支配树

【题目描述】

给定一个含有 $N$ 个顶点和 $M$ 条边的有向图。第 $i$ 条边为 $(a_i, b_i)$。

计算这个以 $S$ 为根的图的支配树。

【输入】

输入格式如下：

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

第一行包含三个整数 $N$、$M$、$S$。接下来 $M$ 行，第 $i$ 行包含两个整数 $a_i$、$b_i$，表示一条从 $a_i$ 到 $b_i$ 的有向边。

【输出】

输出格式如下：

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

输出 $N$ 个整数 $p_0$、$p_1$、$p_2$、……、$p_{N-1}$。

$p_i$ 是顶点 $i$ 的父亲。如果无法从 $S$ 到达顶点 $i$，输出 $-1$。$p_S$ 是 $S$。

【输入样例】

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

【输出样例2】

4 0 4 4 4 3 3 -1

【数据范围】

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

【来源】

Library Checker（yosupo06） dominatortree