#P18146. Graph Weighting

Graph Weighting

Graph Weighting

给定一个 NN 个点、MM 条边的连通无向图,第 ii 条边连接 uiu_i 与 viv_i。图中可能有重边,但没有自环。

对每个 W=0,1,…,KW=0,1,\dots,K,解决以下问题:

判断是否存在一种给第 ii 条边赋权 wi∈{0,1,…,L}w_i\in\{0,1,\dots,L\} 的方式,使得图中任意一棵生成树的边权和都恰好为 WW。若存在,求出所有满足条件的赋值中

w12+w22+⋯+wM2w_1^2+w_2^2+\dots+w_M^2

的最小值。

输入格式

第一行四个整数 N,M,K,LN,M,K,L(2≤N≤1052\le N\le 10^5,N−1≤M≤2⋅105N-1\le M\le 2\cdot 10^5,1≤L,K≤1051\le L,K\le 10^5)。

接下来 MM 行,每行两个整数 ui,viu_i,v_i(1≤ui,vi≤N1\le u_i,v_i\le N,ui≠viu_i\ne v_i)。

输出格式

按 W=0,1,…,KW=0,1,\dots,K 的顺序输出 K+1K+1 个整数,用空格分隔。若不存在合法赋值输出 -1,否则输出最小的平方和。

样例 1

输入:

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

输出:

0 1 3 4

例如 W=2W=2 时,取 (w1,w2,w3,w4)=(0,1,1,1)(w_1,w_2,w_3,w_4)=(0,1,1,1),任意生成树的权值都是 2。

样例 2

输入:

2 3 2 1
1 2
2 1
1 2

输出:

0 3 -1

样例 3

输入:

6 7 9 2
1 2
2 3
2 4
4 5
4 6
1 4
3 4

输出:

0 1 2 5 6 7 10 13 22 25