当前没有测试数据。

E - 计数简单路径

分数：$500$ 分

问题描述

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

输出

输出答案。

4 2
1 2
2 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