AT_ndpc2026_b DAG

给定一个包含 $N$ 个顶点和 $M$ 条边的简单有向图，顶点编号从 $1$ 到 $N$。第 $i$ 条边从顶点 $u_i$ 指向顶点 $v_i$。 **该图保证没有环（即为有向无环图，DAG）**。 请计算从顶点 $1$ 到顶点 $N$ 的路径条数，结果需对 $998244353$ 取模。 一共给出 $T$ 组测试数据。请分别输出每组数据的答案。

输入从标准输入给出，格式如下： > $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 对于第一组测试数据，从顶点 $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 \ne j$，则 $(u_i, v_i) \ne (u_j, v_j)$ - 图保证为简单有向无环图 - 所有测试数据中 $N$ 的总和不超过 $2 \times 10^5$ - 所有测试数据中 $M$ 的总和不超过 $2 \times 10^5$ - 所有输入均为整数。 由 ChatGPT 5 翻译