分数: 600 点
问题陈述
给你一个简单的连通无向图 N 顶点编号 1 to 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