102844: [AtCoder]ABC284 E - Count Simple Paths

Problem Statement

You are given a simple undirected graph with $N$ vertices numbered $1$ to $N$ and $M$ edges numbered $1$ to $M$. Edge $i$ connects vertex $u_i$ and vertex $v_i$. The degree of each vertex is at most $10$.
Let $K$ be the number of simple paths (paths without repeated vertices) starting from vertex $1$. Print $\min(K, 10^6)$.

Constraints

• $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$
• The given graph is simple.
• The degree of each vertex in the given graph is at most $10$.
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

4 2
1 2
2 3

Sample Output 1

3

We have the following three paths that count. (Note that a path of length $0$ also counts.)

• Vertex $1$;
• vertex $1$, vertex $2$;
• vertex $1$, vertex $2$, vertex $3$.

Sample Input 2

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

Sample Output 2

16

Sample Input 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

Sample Output 3

2023

问题描述

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