Задача A. Родительское собрание Имя входного файла: стандартный поток ввода

Имя выходного файла: стандартный поток вывода

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мебибайт

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

них самую интересную и самую неинтересную по своему вкусу.

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

самую понравившуюся ей идею и больше в обсуждении не участвует. Если среди родителей

нет ни одного недовольного (считающего эту идею самой неинтересной), идея принимается,

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

самую интересную, по их мнению, идею. Однако, поскольку они говорят хором, то слышно

только самого голосистого из них, и предложенная им или ей идея становится очередным

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

повторяется.

Родители в Генином классе упорные, и классный руководитель уже устала ждать конца

собрания... Определите, смогут ли родители когда-нибудь договориться!

Формат входных данных

В первой строке записаны три натуральных числа N, M и S (N — количество родителей,

M > 2 — количество идей, S — номер идеи, предложенной классным руководителем). Идеи

пронумерованы последовательными натуральными числами, начиная с единицы.

В каждой из следующих N строк записана пара различных чисел bi

, wi

, разделённых пробелом — номер самой интересной и номер самой неинтересной идеи по мнению i-го родителя.

Информация о родителях дана в порядке строгого убывания их голосистости.

Формат выходных данных

Выведите одно число — номер идеи, выбранной родителями. Если родители не смогут

прийти к общему мнению и классному руководителю придётся вмешаться, выведите 0.

Примеры

стандартный поток ввода стандартный поток вывода

2 3 1

2 1

3 2

3

2 2 1

2 1

1 2

0

Подзадача 1 ( : 30)

N, M 6 1000.

Подзадача 2 ( : 70)

N, M 6 105

Решение в Free Паскале 2.6.4