← 返回题目列表

AtCoder · utpc2023_g

G. 图权重

中文机器翻译题面 查看原题

配点 : 100 点

問題文

在顶部 编号为 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
  • 给出的无向图是连通的

入力

输入是按以下格式从标准输入给出的。

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 的最小值。


入力例 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