도미네이터 트리

$N$개의 정점과 $M$개의 간선을 갖는 유향 그래프가 주어진다. $i$번째 간선은 $(a_i, b_i)$이다.

$S$를 루트로 하는 이 그래프의 도미네이터 트리를 계산한다.

제한 조건

• $1 \leq N \leq 200,000$
• $0 \leq M \leq 200,000$
• $0 \leq S, a_i, b_i < N$

$N$ $M$ $S$
$a_0$ $b_0$
$a_1$ $b_1$
:
$a_{M - 1}$ $b_{M - 1}$

$p_0$ $p_1$ $p_2$ ... $p_{N - 1}$

$p_i$은 정점 $i$의 부모이다. $S$에서 $i$에 도달할 수 없다면 $-1$을 출력한다. $p_S$은 $S$이다.