問題文

頂点に 1,2,\ldots,N の番号が付いた N 頂点 M 辺の連結無向グラフがあります。i 番目の辺は頂点 u_i と頂点 v_i を結んでいます。グラフは多重辺をもつ場合がありますが、自己ループはもちません。

W = 0,1,\ldots,K それぞれに対して、以下の問題を解いてください。

各 i (1\leq i\leq M) について i 番目の辺に重み w_i\in \lbrace 0,1,\ldots,L \rbrace を割り当てる方法で、グラフの任意の全域木の重みがちょうど W になるようなものが存在するか判定してください。ただし、全域木の重みとは全域木に含まれる全ての辺の重みの総和のことです。また、存在するならばそのような割り当て全体における (w_1)^2+(w_2)^2+\cdots +(w_M)^2 の最小値を求めてください。

制約

• 入力は全て整数
• 2 \leq N \leq 10^5
• N-1 \leq M \leq 2\times 10^5
• 1 \leq L \leq K \leq 10^5
• 1 \leq u_i, v_i \leq N
• u_i \neq v_i
• 与えられる無向グラフは連結である

入力例 1

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

出力例 1

0 1 3 4

例えば W = 2 のときは (w_1,w_2,w_3,w_4) = (0,1,1,1) とすれば、グラフの任意の全域木の重みは 2 になります。

入力例 2

2 3 2 1
1 2
2 1
1 2

出力例 2

0 3 -1

グラフの任意の全域木の重みを 2 にすることはできません。

与えられるグラフは多重辺をもつ場合があることに注意してください。

入力例 3

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

出力例 3

0 1 2 5 6 7 10 13 22 25