← 返回题目列表

AtCoder · ndpc2026_b

B. 有向无环图

中文机器翻译题面 查看原题

分数: 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