题目描述

给定一个简单无向图，有 $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