#P17834. [Ontak2022]SOC

[Ontak2022]SOC

题目描述

有一棵包含 nn 个房间的树,边代表走廊。树中有 kk 名学生,每个房间至多一名,且任意两个相邻房间不能同时有学生。

另外有 kk 台计算机,每个房间至多一台,且任意两个相邻房间不能同时有计算机。学生可以任意分配到计算机,不区分身份。

一次操作把一名学生沿一条走廊移动到相邻房间。每次操作后,仍需保证每个房间至多一名学生,且相邻房间不能同时有学生。

判断能否让所有学生最终站在有计算机的房间中;若能,输出至多 4n24n^2 次操作。无须最小化操作数。

输入格式

第一行一个整数 zz,表示测试组数。

每组先输入一个整数 nn,随后 n−1n-1 行给出树边端点 ui,viu_i,v_i。再输入一个整数 kk。

接下来一行按严格递增顺序给出学生初始位置 s1,…,sks_1,\ldots,s_k;再下一行按严格递增顺序给出计算机位置 c1,…,ckc_1,\ldots,c_k。

输出格式

每组先输出一行 YES 或 NO。

如果输出 YES,下一行输出操作数 MM,满足 1≤M≤4n21\le M\le4n^2。随后 MM 行,每行两个整数 ai,bia_i,b_i,表示把当前位于 aia_i 的学生沿走廊移动到 bib_i。

数据范围

1≤z≤30001\le z\le3000;2≤n≤20002\le n\le2000;1≤k<n1\le k<n;各编号在 [1,n][1,n] 内;输入保证树连通无环,两组位置分别满足不相邻条件,并且至少一名学生初始不在有计算机的房间中。

所有测试组的 n2n^2 之和不超过 4×1074\times10^7。

子任务

子任务 附加限制 分值
1 树是一条路径 15
2 k≤2 16
3 n≤20,测试组数≤200(原表记为t) 17
4 k≤4 18
5 无额外限制 34

样例 1

输入:

2
5
1 2
1 3
2 4
2 5
2
1 4
1 5
7
1 2
2 3
2 4
4 6
6 5
6 7
3
1 4 5
3 4 7

输出:

YES
4
1 3
4 2
2 5
3 1
NO