有向图生成树计数

【题目描述】

给定一个有向图，包含 $N$ 个顶点和 $M$ 条边。第 $i$ 条边从顶点 $u_i$ 指向顶点 $v_i$。这个图不一定是简单图。

同时给定一个顶点 $r$。

求以顶点 $r$ 为根的有向生成树的数量（这意味着所有顶点都必须能从 $r$ 到达），对 $998244353$ 取模。

【输入】

$N$ $M$ $r$
$u_0$ $v_0$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{M-1}$ $v_{M-1}$

【输出】

输出以 $r$ 为根的有向生成树的数量对 $998244353$ 取模的结果。

【输入样例】

3 5 2
0 1
0 1
1 2
2 1
2 0

【输出样例】

3

【输入样例2】

1 2 0
0 0
0 0

【输出样例2】

1

【输入样例3】

4 4 3
0 1
1 0
2 3
3 2

【输出样例3】

0

【输入样例4】

4 8 2
0 1
0 3
2 1
3 1
3 0
3 0
2 3
1 3

【输出样例4】

8

【数据范围】

• $1 \leq N \leq 500$
• $0 \leq M \leq 500000$
• $0 \leq r \lt N$
• $0 \leq u_i \lt N$
• $0 \leq v_i \lt N$

【来源】

Library Checker（yosupo06） counting_spanning_tree_directed