分数: 2 点
问题陈述
给你一个简单的有向图 N 顶点和 M 边缘。顶点编号从 1 to N。的 i- 第一条边从顶点出发 u_i 到顶点 v_i.
该图没有循环。
查找从顶点开始的路径数 1 到顶点 N,模数 998244353.
你被给予 T 测试用例。解决它们中的每一个。
约束
- 1 \leq T \leq 10^5
- 2 \leq N \leq 2 \times 10^5
- 0 \leq M \leq \min\left(\frac{N(N-1)}{2}, 2 \times 10^5\right)
- 1 \leq u_i \leq N
- 1 \leq v_i \leq N
- If i \neq j,那么 (u_i, v_i) \neq (u_j, v_j)
- 给定的图是一个没有循环的简单有向图
- 总和 N 所有测试用例最多 2 \times 10^5
- 总和 M 所有测试用例最多 2 \times 10^5
- 所有输入值均为整数
输入
输入由标准输入给出,格式如下:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出:
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
输出
打印 T 行。对于 i第行,输出答案 i- 第一个测试用例。
总共
对于每个测试用例,输出来自顶点的路径数 1 到顶点 N,模数 998244353.
示例输入 1
3 4 4 1 2 2 3 3 4 2 4 5 4 1 2 2 3 4 5 1 3 7 18 1 6 1 4 6 4 6 3 4 3 1 5 6 5 4 5 3 5 1 2 6 2 4 2 3 2 5 2 6 7 4 7 5 7 2 7
示例输出 1
2 0 24
对于第一个测试用例,有 2 从顶点开始的路径 1 到顶点 4:
- 顶点 1 \to 顶点 2 \to 顶点 3 \to 顶点 4
- 顶点 1 \to 顶点 2 \to 顶点 4