eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Одинокий остров

Одинокий остров

Лимит времени 2 секунды
Лимит использования памяти 128 MiB

Имеется множество островов, соединенных односторонними мостами: если мост соединяет острова a и b, то мост может быть использован только для перехода от a к b, Вы не можете вернуться назад по этому мосту. Когда Вы находитесь на острове a, то выбираете (равномерно и случайным образом) один из островов, на который можно напрямую попасть с a через односторонний мост, и переходите на этот остров. Вы застряните на острове, если нельзя двигаться дальше. Гарантируется, что после того, как Вы покинете какой-либо остров, то на него уже не сможете вернуться.

Найдите остров, на котором Вы застряните с наибольшей вероятностью. Два острова считаются одинаково вероятными, если абсолютная разность вероятностей попадания на них ≤ 10^{-9}.

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

Первая строка содержит три целых числа: количество островов n~(1 \le n \le 200000), количество односторонних мостов m~(1 \le m \le 500000) и номер r~(1 \le r \le n) острова на котором Вы сначала находитесь. Каждая из следующих m строк содержит два целых числа u_i и v_i~(1 \le u_i, v_i \le n) описывающих односторонний мост из u_i в v_i.

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

Выведите номер острова, на котором Вы застряните с наибольшей вероятностью. Если существует несколько таких островов, то выведите их в порядке возрастания индексов (значения, разделенные пробелом в одной строке).

Пример

Входные данные #1
5 7 1
1 2
1 3
1 4
1 5
2 4
2 5
3 4
Выходные данные #1
4