#P18146. Graph Weighting
Graph Weighting
Graph Weighting
给定一个 个点、 条边的连通无向图,第 条边连接 与 。图中可能有重边,但没有自环。
对每个 ,解决以下问题:
判断是否存在一种给第 条边赋权 的方式,使得图中任意一棵生成树的边权和都恰好为 。若存在,求出所有满足条件的赋值中
的最小值。
输入格式
第一行四个整数 (,,)。
接下来 行,每行两个整数 (,)。
输出格式
按 的顺序输出 个整数,用空格分隔。若不存在合法赋值输出 -1,否则输出最小的平方和。
样例 1
输入:
4 4 3 2
1 2
2 3
2 4
3 4
输出:
0 1 3 4
例如 时,取 ,任意生成树的权值都是 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