支配树（Dominator Tree）

问题描述

给定一个含 $N$ 个顶点、$M$ 条边的有向图，以及一个根节点 $S$（$0 \le S < N$）。
求该图关于根 $S$ 的支配树（Dominator Tree）：

• 顶点 $u$ 支配 顶点 $v$（记作 $u \gg v$），若从 $S$ 到 $v$ 的每条路径都经过 $u$；
• 支配树中，每个非根顶点 $i$ 的父节点 $p_i$ 是其直接支配者（immediate dominator），即除 $i$ 自身外，支配 $i$ 且被所有其他支配 $i$ 的顶点所支配的唯一顶点；
• 若 $i$ 不可达自 $S$，则 $p_i = -1$；根节点 $S$ 满足 $p_S = 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\ \cdots\ p_{N-1}$

$p_i$ 是顶点 $i$ 在支配树中的父节点：若 $i$ 不可达自 $S$，则 $p_i = -1$；否则 $p_i$ 为其直接支配者；特别地，$p_S = S$。

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

0 0 1 0 0

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