Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

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

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

[Все попытки] [Лучшие попытки]

 
     
Югорский НИИ ИТ, Югорский ФМЛ