Теофанис хочет играть в видеоигры, но при этом он должен заботиться о своей сестре. Поскольку Теофанис учится на программиста, он нашел способ делать и то, и другое. Он установит в своем доме несколько камер, чтобы убедиться, что с его сестрой все в порядке.

Его дом — это неориентированный граф с $$$n$$$ вершинами и $$$m$$$ ребрами. Его сестра любит играть на ребрах графа, поэтому он должен установить камеру хотя бы в одном из концов каждого ребра графа. Теофанис хочет найти вершинное покрытие, которое максимизирует минимальную разницу между номерами выбранных вершин.

Более формально, пусть $$$a_1, a_2, \ldots, a_k$$$ — вершинное покрытие графа. Пусть минимальная разница между номерами выбранных вершин — это минимальное $$$\lvert a_i - a_j \rvert$$$ (где $$$i \neq j$$$) среди вершин, которые вы выбрали. Если $$$k = 1$$$, то считаем, что минимальная разница между номерами выбранных вершин равна $$$n$$$.

Можете ли вы найти максимально возможную минимальную разницу между номерами выбранных вершин?