# Dominator Tree

AC一覧

## Problem Statement問題文

Given a directed graph with $N$ vertices and $M$ edges. $i$-th edge is $(a_i, b_i)$.

Calculate the dominator tree of this graph whose root is $S$.

$N$ 頂点 $M$ 辺の有向グラフが与えられる。$i$ 番目の辺は頂点 $a_i$ から $b_i$ に貼られている。

## Constraints制約

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

## Input入力

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


## Output出力

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


$p_i$ is the parent of vertex $i$. If we can not reach $i$ from $S$, print $-1$. $p_S$ is $S$.

$p_i$ は頂点 $i$ の親である。頂点 $S$ から頂点 $i$ へ到達できない場合、$-1$ を出力。また、$p_S = S$ とすること。

## Sampleサンプル

### # 1

5 6 0
0 1
1 2
2 3
3 4
0 3
2 4

0 0 1 0 0


### # 2

8 8 4
4 2
4 3
2 0
3 0
0 1
3 5
3 6
7 6

4 0 4 4 4 3 3 -1


Timelimit: 5 secs

Before submitting, please confirm terms and conditions