AT_ndpc2026_b.DAG

You are given a simple directed graph with $N$ vertices and $M$ edges. The vertices are numbered from $1$ to $N$. The $i$-th edge goes from vertex $u_i$ to vertex $v_i$.
This graph has no cycles.

Find the number of paths from vertex $1$ to vertex $N$, modulo $998244353$.

You are given $T$ test cases. Solve each of them.

给你一个包含 $N$ 个顶点和 $M$ 条边的有向无环图（DAG）。顶点编号为 $1$ 到 $N$。第 $i$ 条边从顶点 $u_i$ 指向顶点 $v_i$。
该图不含环。

求从顶点 $1$ 到顶点 $N$ 的路径数量，结果对 $998244353$ 取模。

你将得到 $T$ 组测试数据。请分别求解每组数据。

The input is given from standard input in the following format:

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format:

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

输入从标准输入中按以下格式给出：

$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$

Print $T$ lines. For the $i$-th line, output the answer for the $i$-th test case.
For each test case, output the number of paths from vertex $1$ to vertex $N$, modulo $998244353$.

输出 $T$ 行。第 $i$ 行输出第 $i$ 个测试用例的答案。
对于每个测试用例，输出从顶点 $1$ 到顶点 $N$ 的路径数量，对 $998244353$ 取模。

Sample 1 Explanation:
For the first test case, there are $2$ paths from vertex $1$ to vertex $4$:

• vertex $1$ $\to$ vertex $2$ $\to$ vertex $3$ $\to$ vertex $4$
• vertex $1$ $\to$ vertex $2$ $\to$ vertex $4$

Constraints

• $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$, then $(u_i, v_i) \neq (u_j, v_j)$
• The given graph is a simple directed graph with no cycles
• The sum of $N$ over all test cases is at most $2 \times 10^5$
• The sum of $M$ over all test cases is at most $2 \times 10^5$
• All input values are integers

样例 1 解释：
对于第一个测试用例，从顶点 $1$ 到顶点 $4$ 共有 $2$ 条路径：

• 顶点 $1$ $\to$ 顶点 $2$ $\to$ 顶点 $3$ $\to$ 顶点 $4$
• 顶点 $1$ $\to$ 顶点 $2$ $\to$ 顶点 $4$

约束条件

• $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$
• 若 $i \neq j$，则 $(u_i, v_i) \neq (u_j, v_j)$
• 给定图是一个无环的简单有向图
• 所有测试用例中 $N$ 的总和不超过 $2 \times 10^5$
• 所有测试用例中 $M$ 的总和不超过 $2 \times 10^5$
• 所有输入值均为整数