새 관찰

Kiara는 아주 특이한 방식으로 이동하는 신기한 조류를 연구한다. 이들의 이동은 그래프의 언어로 설명하는 것이 가장 좋다. 노드가 나무인 방향 그래프 $G$가 있고, 새는 $(T_a, T_b)$가 $G$의 간선일 때에만 나무 $T_a$에서 $T_b$로 날아갈 수 있다.

Kiara는 이 새들의 비행을 지배하는 실제 그래프 $G$를 알지 못하지만, 이전 현장 연구에서 많은 새의 이동 데이터를 수집했다. 이를 이용해 새들이 어떻게 움직이는지 설명하는 그래프 $P$를 고안했다. Kiara는 새를 너무 오래 관찰한 나머지, 새가 $a$에서 $b$로 직접 날아갈 수 있다면 그러한 사건을 적어도 한 번 목격했다고 확신한다. 그러나 새가 $a$에서 $b$를 거쳐 $c$로 날아갔는데 그녀가 경유지 $a$와 $c$만 목격하고 $(a, c)$를 $P$에 추가했을 가능성이 있다. 새가 $a$에서 $b$를 거쳐 $c$를 거쳐 $d$로 날아갔는데 그녀가 $a$와 $d$만 목격하고 $(a, d)$를 $P$에 추가했을 가능성도 있다. 정리하자면, 그녀는 $P$가 $G$의 모든 간선을 포함하며, $P$에는 $G$에서 $a$에서 $b$로 가는 경로가 존재하는 다른 간선 $(a, b)$가 포함되어 있을 수도 있다는 것을 안다(단, $P$가 그러한 간선을 모두 포함하지는 않을 수 있다).

다음 현장 연구를 위해 Kiara는 주어진 나무 $T$ 옆에 기지를 설치하기로 했다. $T$에 새가 도착하는 것을 경고받기 위해, 그녀는 새가 올 수 있는 나무, 즉 $G$에 간선 $(T', T)$가 존재하는 나무 $T'$에 탐지기를 설치하고 싶어 한다. 탐지기는 저렴하지 않으므로, 그녀는 $(T', T)$가 $G$에 속한다고 확신하는 나무 $T'$에만 탐지기를 설치하려 한다.

Kiara는 $(a, b)$가 $P$의 간선이고 $P$에서 $a$에서 시작해 $b$에서 끝나는 모든 경로가 간선 $(a, b)$를 사용할 때, 간선 $(a, b)$가 $G$에 속한다고 확신한다. Kiara는 $(T', T)$가 $G$의 간선이라고 확신하는 나무 $T'$의 집합 $S(T)$를 계산해 달라고 요청한다.

입력은 그래프 $P$를 설명한다. 첫째 줄에는 공백으로 구분된 세 정수 $N$, $M$, $T$가 주어진다. $N$은 $P$의 노드 수, $M$은 $P$의 간선 수, $T$는 Kiara가 기지를 설치할 나무에 대응하는 노드이다.

다음 $M$개의 줄은 그래프 $P$의 간선을 설명한다. 각 줄에는 공백으로 구분된 두 정수 $a$와 $b$($0 \le a, b < N$, $a \ne b$)가 주어지며, $(a, b) \in P$임을 나타낸다. 같은 쌍 $(a, b)$가 두 번 나타나지 않음이 보장된다.

출력은 집합 $S(T)$를 설명해야 한다. 첫째 줄에는 $S(T)$의 노드 수 $L$이 주어지고, 이어서 $L$개의 줄에 $S(T)$의 서로 다른 원소가 각각 하나씩 주어진다. $S(T)$의 원소는 증가하는 순서로, 한 줄에 하나씩 출력해야 한다.

• $1 \le N, M \le 100\,000$;
• $0 \le T < N$.