← 返回题目列表

AtCoder · abc284_e

H. 计算简单路径

中文机器翻译题面 查看原题

分数: 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