AT_ndpc2026_b DAG

頂点に $ 1 $ から $ N $ の番号が付いた $ N $ 頂点 $ M $ 辺の単純有向グラフがあります。 $ i $ 番目の辺は頂点 $ u_i $ から頂点 $ v_i $ へ向かう辺です。 **このグラフには閉路がありません。** 頂点 $ 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 $ で割った余りを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて、頂点 $ 1 $ から頂点 $ 4 $ へ向かうパスは次の $ 2 $ 本です。 - 頂点 $ 1 $ $ \to $ 頂点 $ 2 $ $ \to $ 頂点 $ 3 $ $ \to $ 頂点 $ 4 $ - 頂点 $ 1 $ $ \to $ 頂点 $ 2 $ $ \to $ 頂点 $ 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 $ - $ i \neq j $ ならば $ (u_i, v_i) \neq (u_j, v_j) $ - 入力で与えられるグラフは閉路のない単純有向グラフ - 全てのテストケースに対する $ N $ の総和は $ 2 \times 10^5 $ 以下 - 全てのテストケースに対する $ M $ の総和は $ 2 \times 10^5 $ 以下 - 入力される値は全て整数