问题描述

给定一个简单无向图，包含$N$个顶点（编号为$1$到$N$）和$M$条边（编号为$1$到$M$）。第$i$条边连接顶点$u_i$和顶点$v_i$。每个顶点的度数不超过$10$。设$K$为从顶点$1$出发的简单路径（不重复经过顶点的路径）的数量。输出$\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

有以下三条符合条件的路径（注意长度为$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