Спостереження за птахами#9712

Спостереження за птахами

1 секунда

128 мегабайтів

Складна

Кьяра вивчає незвичайний вид птахів, які пересуваються дуже своєрідним чином. Їх пересування найзручніше описувати мовою графів: існує орієнтований граф $G$ , у якому вершини відповідають деревам, і птах може перелетіти з дерева $T_{a}$ T_a на дерево $T_{b}$ T_b тільки в тому випадку, якщо в графі $G$ існує ребро $(T_{a}, T_{b})$ (T_a, T_b).

Кьяра не знає точний вигляд графа $G$ , що описує пересування птахів, але під час попередніх польових спостережень вона зібрала дані про подорожі багатьох птахів. На основі цих даних вона побудувала граф $P$ , що відображає, як, за її спостереженнями, птахи переміщуються. Кьяра настільки ретельно стежила за птахами, що впевнена: якщо птах міг перелетіти напряму з $a$ в $b$ , то вона принаймні один раз зафіксувала такий переліт. Проте можливо, що птах перелетів із $a$ в $b$ , потім у $c$ , а Кьяра помітила лише точки $a$ і $c$ , після чого додала ребро $(a, c)$ у граф $P$ . Також можливо, що птах пролетів маршрут $a \to b \to c \to d$ a \rightarrow b \rightarrow c \rightarrow d, а Кьяра помітила лише $a$ і $d$ і додала $(a, d)$ у $P$ , і так далі. Загалом, Кьяра знає, що граф $P$ містить усі ребра графа $G$ , і що він може містити деякі додаткові ребра $(a, b)$ , для яких у графі $G$ існує шлях із $a$ в $b$ (при цьому $P$ не зобов'язаний містити всі такі ребра).

У своєму наступному польовому дослідженні Кьяра вирішила розмістити базу поруч із заданим деревом $T$ . Щоб бути заздалегідь попередженою про наближення птахів до дерева $T$ , вона хоче встановити детектори на деревах, звідки птахи можуть прилетіти (тобто на таких деревах $T^{'}$ T', що в графі $G$ існує ребро $(T^{'}, T)$ (T', T)). Оскільки детектори дорогі, вона хоче встановлювати їх тільки на ті дерева $T^{'}$ T', для яких вона впевнена, що $(T^{'}, T)$ (T', T) дійсно є ребром графа $G$ .

Кьяра впевнена, що ребро $(a, b)$ належить графу $G$ , якщо $(a, b)$ є ребром графа $P$ і всі шляхи в $P$ , що починаються в $a$ і закінчуються в $b$ , використовують ребро $(a, b)$ . Кьяра просить вас обчислити множину $S (T)$ дерев $T^{'}$ T', для яких вона впевнена, що $(T^{'}, T)$ (T', T) є ребром графа $G$ .

Вхідні дані

Вхідні дані описують граф $P$ . Перший рядок містить три цілих числа: $N, M (1 \leq N, M \leq 1 0^{5})$ N, M~(1 \le N, M \le 10^5) і $T (0 \leq T < N)$ T~(0 \le T < N). Тут $N$ — кількість вершин у графі $P$ , $M$ — кількість ребер у графі $P$ , а $T$ — вершина, що відповідає дереву, поруч з яким Кьяра встановить свою базу.

Наступні $M$ рядків описують ребра графа $P$ . Кожна з них містить два цілих числа $a$ і $b$ ( $0 \leq a, b < N$ 0 \le a, b < N і $a \neq = b$ a \ne b), що означають, що $(a, b) \in P$ (a, b) \in P. Гарантовано, що одна й та сама пара $(a, b)$ не зустрінеться більше одного разу.

Вихідні дані

Виведіть множину $S (T)$ . Перший рядок повинен містити одне ціле число $L$ — кількість вершин у $S (T)$ , за яким слідують $L$ рядків, кожен з яких містить один елемент множини $S (T)$ . Елементи множини $S (T)$ повинні бути виведені у порядку зростання, по одному елементу в рядку.

Приклади

Пояснення до прикладу 1. Вершина $1$ належить $S (2)$ , тому що (єдиний) шлях від $1$ до $2$ використовує ребро $(1, 2)$ . Вершина $0$ не належить $S (2)$ , оскільки шлях $0 \to 1 \to 2$ 0 \rightarrow 1 \rightarrow 2 не використовує ребро $(0, 2)$ .

Пояснення до прикладу 2. З тієї ж причини, що й у прикладі $1$ , вершина $0$ не належить $S (2)$ , тоді як вершина $1$ належить. Вершини $3$ і $5$ не належать $S (2)$ , оскільки у графі немає ребер $(3, 2)$ або $(5, 2)$ . Нарешті, вершина $4$ належить $S (2)$ , тому що всі шляхи від $4$ до $2$ проходять через ребро $(4, 2)$ .

Приклад 1

Приклад 2