Региональная олимпиада по программированию среди студентов 1-6 курсов 2017. Командный тур

Соревнование завершилось 13.05.17 в 15:03

A. Желоб

Ограничение по времени: 2 с.
Ограничение по памяти: 256 МБ

В продолговатом желобе размещены один за другим n кубических грузиков с крючками на верхней стороне. Некоторые пары крючков соединены между собой прочными нитями.

image

Максим стоит возле желоба так, что видит все грузики. Он начинает тянуть ближайший грузик вдоль желоба на себя. Считая, что грузики занумерованы последовательными целыми положительными числами от ближайшего к Максиму до самого дальнего, определите максимальный из номеров грузиков, которые будут сдвинуты.

Максим достаточно силён, чтобы сдвинуть любое количество грузиков, а соединяющие их нити никогда не рвутся.

Входные данные

В первой строке входных данных содержится два целых числа n и m, разделённых одним пробелом — количество грузиков и количество нитей (1 \leqslant n \leqslant 10^{9}, 1 \leqslant m \leqslant 10^{5}).

Последующие m строк содержат по два разделённых пробелом целых числа a_{i} и b_{i} — номера соединённых i-той нитью грузиков (1 \leqslant a_{i}, b_{i} \leqslant n).

Выходные данные

Выходные данные должны содержать единственное целое число — максимальный из номеров всех грузиков, которые Максим потянет на себя вместе с первым.

Примеры
Стандартный вводСтандартный вывод
5 2
1 3
4 2
4
Пояснения к примерам

Рисунок в условии иллюстрирует приведённый пример.