E - Count Simple Paths Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

頂点に 1 から N の番号が、辺に 1 から M の番号がついた N 頂点 M 辺の単純無向グラフが与えられます。辺 i は頂点 u_i と頂点 v_i を結んでいます。また、各頂点の次数は 10 以下です。
頂点 1 を始点とする単純パス(同じ頂点を複数回通らないパス)の個数を K とします。\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

条件を満たすパスは次の 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

Score : 500 points

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