分数: 500 点
问题陈述
给你一个简单的无向图 N 顶点编号 1 to N 和 M 边编号 1 to 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