

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