#P19008. 【CodeChef START263A】Consistentree (Construct)
【CodeChef START263A】Consistentree (Construct)
题目描述
给定一棵包含 个顶点的树,顶点编号为 到 。顶点 的权值 为 、 或 。
给每个顶点分配一个标签,要求 到 中的每个整数恰好使用一次。若分配后每个顶点 都满足对应的条件,就称这棵树为一致的。
- 时, 的标签小于它的每个相邻顶点的标签。
- 时, 的标签大于它的每个相邻顶点的标签。
- 时, 至少有一个相邻顶点的标签比它小,并且至少有一个相邻顶点的标签比它大。
判断给定的树是否一致。若一致,输出任意一种满足要求的标签分配。
输入格式
第一行包含一个整数 ,表示测试用例数。
对于每组测试用例,第一行包含一个整数 。第二行包含 个以空格分隔的整数 。
接下来的 行,每行包含两个以空格分隔的整数 ,表示顶点 与 之间有一条边。
输出格式
每组测试用例输出一行。
- 若无法满足要求,输出 。
- 若可以满足要求,输出 个以空格分隔的整数 ,其中 为分配给顶点 的标签。若有多种合法分配,输出任意一种即可。
数据范围
- 。
- 。
- 。
- ,给出的边构成一棵树。
- 所有测试用例的 之和不超过 。
样例输入
5
2
0 1
1 2
4
-1 0 0 1
1 2
2 3
3 4
5
0 -1 1 -1 1
1 2
1 3
1 4
1 5
5
0 1 1 1 1
1 2
1 3
1 4
1 5
7
-1 1 -1 0 1 -1 1
1 2
2 3
2 4
4 5
4 6
3 7
样例输出
-1
1 2 3 4
3 1 4 2 5
-1
1 6 2 5 7 3 4
样例说明
第一组中,顶点 的权值为 ,但它只有一个相邻顶点,无法同时满足两种大小关系。
第三组的样例分配给顶点 的标签为 。顶点 和 的标签小于 ,顶点 和 的标签大于 。
第四组中,顶点 的所有相邻顶点的权值都为 ,所以它们的标签都必须大于顶点 的标签。这与顶点 的要求冲突。
相关
在下列比赛中: