#P18050. 77G Network

77G Network

77G Network

给定一棵以 11 为根、包含 nn 个顶点的树。你要选出一些顶点,使每条树边的至少一个端点被选中。

还有 mm 条故障约束。约束 (x,y)(x,y) 表示:如果选中了 xx,那么 xx 的子树中与 xx 的距离恰为 yy 的所有顶点都不能选中。这里距离指树路径的边数。

判断是否存在满足全部条件的选择方案;如果存在,输出任意一种。

输入格式

第一行是测试用例数 TT,1≤T≤10001\le T\le1000。每个用例包含:

  • 一行一个整数 nn,2≤n≤2×1052\le n\le2\times10^5。
  • 一行 n−1n-1 个整数 f2,…,fnf_2,\ldots,f_n,其中 1≤fi<i1\le f_i<i,表示顶点 ii 的父亲。
  • 一行一个整数 mm,0≤m≤2×1050\le m\le2\times10^5。
  • 接下来 mm 行,每行两个整数 x,yx,y,1≤x,y≤n1\le x,y\le n。

同一约束可能重复出现。一个输入文件内,所有用例的 nn 之和、mm 之和分别不超过 2×1052\times10^5。

输出格式

无解时输出一行 No。有解时先输出一行 Yes,再输出选中的顶点数 cc,然后输出 cc 个互不相同的顶点编号。

任意满足条件的方案均可。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