G - Count Simple Paths 2 Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 600 点

問題文

頂点に 1 から N の番号がついた N 頂点 M 辺の単純連結無向グラフが与えられます。i 番目の辺は頂点 u_i と頂点 v_i を結んでいます。

各 k=1,2,\ldots,N-1 に対して、頂点 1 から頂点 N までの単純パスであって、パスに含まれる辺の個数が k であるようなものの個数を求めてください。

制約

  • 2\leq N\leq 2\times 10^5
  • N-1\leq M\leq N+20
  • 1\leq u_i\lt v_i\leq N
  • 与えられるグラフは単純連結無向グラフ
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

答えを以下の形式で出力せよ。

\mathrm{ans}_1 \mathrm{ans}_2 \ldots \mathrm{ans}_{N-1}

\mathrm{ans}_i は頂点 1 から頂点 N までの単純パスであって、パスに含まれる辺の個数が i であるようなものの個数である。

入力例 1

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

出力例 1

0 1 2 1

各 k=1,2,3,4 について、頂点 1 から頂点 5 までの単純パスであって、パスに含まれる辺の個数が k であるようなものは以下の通りです。

  • k=1 : 存在しない
  • k=2 : 1\to 3\to 5
  • k=3 : 1\to 2\to 4\to 5 および 1\to 3\to 4\to 5
  • k=4 : 1\to 2\to 4\to 3\to 5

入力例 2

11 15
1 2
1 3
2 3
3 4
3 5
4 5
5 6
5 7
6 7
7 8
7 9
8 9
9 10
9 11
10 11

出力例 2

0 0 0 0 1 5 10 10 5 1

入力例 3

7 18
6 7
4 5
1 7
2 7
1 4
2 5
4 6
2 3
5 6
5 7
1 5
2 4
2 6
1 2
1 3
3 4
1 6
3 5

出力例 3

1 3 11 29 50 42

Score : 600 points

Problem Statement

You are given a simple connected undirected graph with N vertices numbered 1 to N and M edges. The i-th edge connects vertices u_i and v_i.

For each k=1,2,\ldots,N-1, find the number of simple paths from vertex 1 to vertex N that contain exactly k edges.

Constraints

  • 2\leq N\leq 2\times 10^5
  • N-1\leq M\leq N+20
  • 1\leq u_i\lt v_i\leq N
  • The given graph is a simple connected undirected graph.
  • All input values 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

Output the answers in the following format:

\mathrm{ans}_1 \mathrm{ans}_2 \ldots \mathrm{ans}_{N-1}

\mathrm{ans}_i is the number of simple paths from vertex 1 to vertex N that contain exactly i edges.

Sample Input 1

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

Sample Output 1

0 1 2 1

For each k=1,2,3,4, the simple paths from vertex 1 to vertex 5 that contain exactly k edges are as follows.

  • k=1 : None
  • k=2 : 1\to 3\to 5
  • k=3 : 1\to 2\to 4\to 5 and 1\to 3\to 4\to 5
  • k=4 : 1\to 2\to 4\to 3\to 5

Sample Input 2

11 15
1 2
1 3
2 3
3 4
3 5
4 5
5 6
5 7
6 7
7 8
7 9
8 9
9 10
9 11
10 11

Sample Output 2

0 0 0 0 1 5 10 10 5 1

Sample Input 3

7 18
6 7
4 5
1 7
2 7
1 4
2 5
4 6
2 3
5 6
5 7
1 5
2 4
2 6
1 2
1 3
3 4
1 6
3 5

Sample Output 3

1 3 11 29 50 42