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.

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 $

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

### Sample Explanation 1 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