AT_abc284_e [ABC284E] Count Simple Paths

[problemUrl]: https://atcoder.jp/contests/abc284/tasks/abc284_e 頂点に $ 1 $ から $ N $ の番号が、辺に $ 1 $ から $ M $ の番号がついた $ N $ 頂点 $ M $ 辺の単純無向グラフが与えられます。辺 $ i $ は頂点 $ u_i $ と頂点 $ v_i $ を結んでいます。また、各頂点の次数は $ 10 $ 以下です。 頂点 $ 1 $ を始点とする単純パス(同じ頂点を複数回通らないパス)の個数を $ K $ とします。$ \min(K,\ 10^6) $ を出力してください。

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

答えを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 0\ \leq\ M\ \leq\ \min\ \left(2\ \times\ 10^5,\ \frac{N(N-1)}{2}\right) $ - $ 1\ \leq\ u_i,\ v_i\ \leq\ N $ - 入力で与えられるグラフは単純グラフ - 入力で与えられるグラフの頂点の次数はすべて $ 10 $ 以下 - 入力される値は全て整数 ### Sample Explanation 1 条件を満たすパスは次の $ 3 $ 個です。(長さが $ 0 $ のパスも数えるのに注意してください。) - 頂点 $ 1 $ - 頂点 $ 1 $, 頂点 $ 2 $ - 頂点 $ 1 $, 頂点 $ 2 $, 頂点 $ 3 $