#P18050. 77G Network
77G Network
77G Network
给定一棵以 为根、包含 个顶点的树。你要选出一些顶点,使每条树边的至少一个端点被选中。
还有 条故障约束。约束 表示:如果选中了 ,那么 的子树中与 的距离恰为 的所有顶点都不能选中。这里距离指树路径的边数。
判断是否存在满足全部条件的选择方案;如果存在,输出任意一种。
输入格式
第一行是测试用例数 ,。每个用例包含:
- 一行一个整数 ,。
- 一行 个整数 ,其中 ,表示顶点 的父亲。
- 一行一个整数 ,。
- 接下来 行,每行两个整数 ,。
同一约束可能重复出现。一个输入文件内,所有用例的 之和、 之和分别不超过 。
输出格式
无解时输出一行 No。有解时先输出一行 Yes,再输出选中的顶点数 ,然后输出 个互不相同的顶点编号。
任意满足条件的方案均可。Yes、No 不区分大小写。
样例
输入:
3
6
1 1 2 2 4
2
1 3
2 1
6
1 1 2 2 4
6
1 1
1 2
1 3
2 1
2 2
2 1
8
1 1 3 1 1 2 4
10
1 2
3 2
1 3
5 1
6 1
3 2
4 1
3 2
5 1
3 1
输出(一种合法答案):
Yes
4
1 3 4 5
No
No