Теофанис хочет играть в видеоигры, но при этом он должен заботиться о своей сестре. Поскольку Теофанис учится на программиста, он нашел способ делать и то, и другое. Он установит в своем доме несколько камер, чтобы убедиться, что с его сестрой все в порядке.
Его дом — это неориентированный граф с \(n\) вершинами и \(m\) ребрами. Его сестра любит играть на ребрах графа, поэтому он должен установить камеру хотя бы в одном из концов каждого ребра графа. Теофанис хочет найти вершинное покрытие, которое максимизирует минимальную разницу между номерами выбранных вершин.
Более формально, пусть \(a_1, a_2, \ldots, a_k\) — вершинное покрытие графа. Пусть минимальная разница между номерами выбранных вершин — это минимальное \(\lvert a_i - a_j \rvert\) (где \(i \neq j\)) среди вершин, которые вы выбрали. Если \(k = 1\), то считаем, что минимальная разница между номерами выбранных вершин равна \(n\).
Можете ли вы найти максимально возможную минимальную разницу между номерами выбранных вершин?
Выходные данные
Для каждого набора входных данных выведите максимум среди минимальных разностей между выбранными вершинами среди всех вершинных покрытий.
Примечание
В первом наборе входных данных мы можем установить камеры в вершинах \(1\), \(3\) и \(7\), поэтому ответ — \(2\).
Во втором наборе входных данных мы можем установить только одну камеру в вершине \(1\), поэтому ответ равен \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
7 6
1 2
1 3
1 4
1 6
2 3
5 7
3 3
1 2
1 3
1 1
2 4
1 2
1 2
2 1
1 1
|
2
3
2
|