简单路径计数

题目描述

给定一个有 $N$ 个顶点(编号 $1$ 到 $N$)和 $M$ 条边(编号 $1$ 到 $M$)的简单无向图。边 $i$ 连接顶点 $u_i$ 和顶点 $v_i$。每个顶点的度数至多为 $10$。

设 $K$ 为从顶点 $1$ 出发的简单路径(不经过重复顶点的路径)的条数。输出 $\min(K, 10^6)$。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出答案。

样例

4 2
1 2
2 3

3

符合条件的路径有以下 3 条。(注意长度为 $0$ 的路径也算。)

顶点 $1$;

顶点 $1$,顶点 $2$;

顶点 $1$,顶点 $2$,顶点 $3$。

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

16

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

2023

数据范围

• $1 \le N \le 2 \times 10^5$
• $0 \le M \le \min \left(2 \times 10^5, \frac{N(N-1)}{2}\right)$
• $1 \le u_i, v_i \le N$
• 给定的图是简单图。
• 给定图中每个顶点的度数至多为 $10$。
• 输入中的所有值都是整数。