#P17927. Memory, Permutation, and Rooted Tree
Memory, Permutation, and Rooted Tree
Memory, Permutation, and Rooted Tree
题目描述
给定一棵有 个顶点、以顶点 为根的树。
对于顶点编号的一个排列 ,若顶点 是 的严格后代,且 在排列中出现在 之前,则称 对 是重要的。
定义 为 到所有对它重要的顶点的最小距离。若不存在这样的顶点,则 。树上距离指简单路径的边数。
现在给出树和数组 ,请恢复能产生这个数组的字典序最小的排列;若不存在,则报告无解。
两个不同排列在第一个不同位置上,数字较小的排列字典序较小。
输入格式
第一行一个整数 ,表示测试数据组数。每组数据:
第一行一个整数 。
第二行 个整数 。
接下来 行,每行两个整数 ,表示树的一条无向边。
输出格式
每组数据输出一行。若有解,输出字典序最小的排列;否则输出 -1。
数据范围
- ,。
- 。输入允许 ,不保证有解。
- ,,输入的边构成一棵树。
- 所有测试数据的 之和不超过 。
样例
3
5
-1 1 -1 -1 -1
1 2
2 3
2 4
1 5
10
0 1 1 1 -1 -1 -1 -1 -1 -1
5 3
4 3
8 4
4 2
4 1
2 10
9 5
5 7
6 1
10
2 -1 -1 -1 1 -1 -1 -1 -1 1
2 6
6 10
5 6
5 7
8 10
3 6
5 4
6 9
1 10
1 3 2 4 5
-1
6 1 2 3 4 5 7 8 9 10