|
Паутина
(Время: 1 сек. Память: 64 Мб Сложность: 38%)
Имеется паутина на плоскости, состоящая из нитей, параллельных осям координат. В основе конструкции паутины лежит бесконечное множество вертикальных нитей, пронумерованных слева направо, начиная с единицы. Смежные вертикальные нити могут быть соединены горизонтальными нитями на некоторой высоте. Для каждой вертикальной нити на определенной высоте может быть не более одного подобного соединения.
На одной из вертикальных нитей, в самом верху (выше всех горизонтальных соединений) находится паук, который начинает свое движение вниз. Натыкаясь на очередную нить, паук меняет свое направление. Движение паука продолжается до тех пор, пока все горизонтальные нити не окажутся выше паука.
По заданной конструкции паутины и начальному расположению паука требуется определить номер нити, на которой окажется паук в конце своего движения.
Входные данные
Первая строка входного файла INPUT.TXT содержит два числа K и M, где K – номер нити, соответствующей начальному положению паука. Далее идут M строк, определяющих горизонтальные соединения, по одному в каждой строке. Каждое такое соединение определяется двумя числами P и H, обозначающие соединение смежных вертикальных нитей с номерами P и P+1 на высоте H. Во входных данных все числа натуральные, имеющие следующие ограничения: K, P, H ≤ 109, M ≤ 105.
Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – ответ на задачу.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 6
1 2
3 4
2 5
3 1
1 4
2 3 | 2 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
