April 17 Graphs contest
Одинокий остров
Имеется множество островов, соединенных односторонними мостами: если мост соединяет острова a и b, то мост может быть использован только для перехода от a к b, Вы не можете вернуться назад по этому мосту. Когда Вы находитесь на острове a, то выбираете (равномерно и случайным образом) один из островов, на который можно напрямую попасть с a через односторонний мост, и переходите на этот остров. Вы застряните на острове, если нельзя двигаться дальше. Гарантируется, что после того, как Вы покинете какой-либо остров, то на него уже не сможете вернуться.
Найдите остров, на котором Вы застряните с наибольшей вероятностью. Два острова считаются одинаково вероятными, если абсолютная разность вероятностей попадания на них ≤ 10^(-9).
Вхідні дані
Первая строка содержит три целых числа: количество островов n (1 ≤ n ≤ 200000), количество односторонних мостов m (1 ≤ m ≤ 500000) и номер r (1 ≤ r ≤ n) острова на котором Вы сначала находитесь. Каждая из следующих m строк содержит два целых числа u[i] и v[i] (1 ≤ u[i], v[i] ≤ n) описывающих односторонний мост из u[i] в v[i].
Вихідні дані
Выведите номер острова, на котором Вы застряните с наибольшей вероятностью. Если существует несколько таких островов, то выведите их в порядке возрастания индексов (значения, разделенные пробелом в одной строке).
Приклад
5 7 1 1 2 1 3 1 4 1 5 2 4 2 5 3 4
4