AT_utpc2023_g Graph Weighting

頂点に $ 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 $ の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ L $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_M $ $ v_M $

$ W = 0,1,\ldots,K $ のときの問題の答えをこの順に空白区切りで出力せよ。より詳細には、条件を満たす割り当てが存在しないならば `-1` を、存在するならば条件を満たす割り当て全体における $ (w_1)^2+(w_2)^2+\cdots +(w_M)^2 $ の最小値を出力せよ。

### Sample Explanation 1 例えば $ W = 2 $ のときは $ (w_1,w_2,w_3,w_4) = (0,1,1,1) $ とすれば、グラフの任意の全域木の重みは $ 2 $ になります。 ### Sample Explanation 2 グラフの任意の全域木の重みを $ 2 $ にすることはできません。 与えられるグラフは多重辺をもつ場合があることに注意してください。 ### Constraints - 入力は全て整数 - $ 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 $ - 与えられる無向グラフは連結である