AT_abc319_g [ABC319G] Counting Shortest Paths

[problemUrl]: https://atcoder.jp/contests/abc319/tasks/abc319_g $ N $ 頂点の無向完全グラフ $ G $ に対して下記の操作を行います。 > 各 $ i\ =\ 1,\ 2,\ \ldots,\ M $ について、頂点 $ u_i $ と 頂点 $ v_i $ を結ぶ無向辺を削除する。 その後の $ G $ において、頂点 $ 1 $ から頂点 $ N $ へのパスが存在するかどうかを判定し、 存在する場合は頂点 $ 1 $ から 頂点 $ N $ への最短パスの個数を $ 998244353 $ で割った余りを求めてください。 ここで、頂点 $ 1 $ から 頂点 $ N $ への最短パスとは、頂点 $ 1 $ から頂点 $ N $ へのパスであって含む辺の本数が最小であるものです。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_M $ $ v_M $

操作後の $ G $ において、頂点 $ 1 $ から頂点 $ N $ へのパスが存在しない場合は `-1` を出力し、 存在する場合は頂点 $ 1 $ から頂点 $ N $ への最短パスの個数を $ 998244353 $ で割った余りを出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 0\ \leq\ M\ \leq\ \min\lbrace\ 2\ \times\ 10^5,\ N(N-1)/2\ \rbrace $ - $ 1\ \leq\ u_i,\ v_i\ \leq\ N $ - $ u_i\ \neq\ v_i $ - $ i\ \neq\ j\ \implies\ \lbrace\ u_i,\ v_i\ \rbrace\ \neq\ \lbrace\ u_j,\ v_j\ \rbrace $ - 入力はすべて整数 ### Sample Explanation 1 操作後の $ G $ における頂点 $ 1 $ から頂点 $ N $ への最短パスは、$ 3 $ 本の辺を含む下記の $ 3 $ 個のパスです。 - 頂点 $ 1 $ $ \rightarrow $ 頂点 $ 2 $ $ \rightarrow $ 頂点 $ 3 $ $ \rightarrow $ 頂点 $ 6 $ - 頂点 $ 1 $ $ \rightarrow $ 頂点 $ 2 $ $ \rightarrow $ 頂点 $ 5 $ $ \rightarrow $ 頂点 $ 6 $ - 頂点 $ 1 $ $ \rightarrow $ 頂点 $ 4 $ $ \rightarrow $ 頂点 $ 5 $ $ \rightarrow $ 頂点 $ 6 $ ### Sample Explanation 2 操作後の $ G $ には辺が $ 1 $ 本もありません。 頂点 $ 1 $ から頂点 $ N $ へのパスが存在しないため `-1` を出力します。