Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Паутина

(Время: 1 сек. Память: 16 Мб Сложность: 38%)
Паутина

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

На одной из вертикальных нитей, в самом верху (выше всех горизонтальных соединений) находится паук, который начинает свое движение вниз. Натыкаясь на очередную нить, паук меняет свое направление. Движение паука продолжается до тех пор, пока все горизонтальные нити не окажутся выше паука.

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

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

Первая строка входного файла INPUT.TXT содержит два числа K и M, где K – номер нити, соответствующей начальному положению паука. Далее идут M строк, определяющих горизонтальные соединения, по одному в каждой строке. Каждое такое соединение определяется двумя числами P и H, обозначающие соединение смежных вертикальных нитей с номерами P и P+1 на высоте H. Во входных данных все числа натуральные, имеющие следующие ограничения: K, P, H ≤ 109, M ≤ 105.

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

В выходной файл OUTPUT.TXT выведите целое число – ответ на задачу.

Примеры

INPUT.TXTOUTPUT.TXT
13 6
1 2
3 4
2 5
3 1
1 4
2 3
2

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483, E-mail: admin@acmp.ru