問題文

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

制約

• $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$ 以下
• 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $u_1$ $v_1$ $u_2$ $v_2$ $\\vdots$ $u_M$ $v_M$

出力

答えを出力せよ。

入力例 1

4 2
1 2
2 3

出力例 1

3

条件を満たすパスは次の $3$ 個です。(長さが $0$ のパスも数えるのに注意してください。)

• 頂点 $1$
• 頂点 $1$, 頂点 $2$
• 頂点 $1$, 頂点 $2$, 頂点 $3$

入力例 2

4 6
1 2
1 3
1 4
2 3
2 4
3 4

出力例 2

16

入力例 3

8 21
2 6
1 3
5 6
3 8
3 6
4 7
4 6
3 4
1 5
2 4
1 2
2 7
1 4
3 5
2 5
2 3
4 5
3 7
6 7
5 7
2 8

出力例 3

2023