#P17834. [Ontak2022]SOC
[Ontak2022]SOC
题目描述
有一棵包含 个房间的树,边代表走廊。树中有 名学生,每个房间至多一名,且任意两个相邻房间不能同时有学生。
另外有 台计算机,每个房间至多一台,且任意两个相邻房间不能同时有计算机。学生可以任意分配到计算机,不区分身份。
一次操作把一名学生沿一条走廊移动到相邻房间。每次操作后,仍需保证每个房间至多一名学生,且相邻房间不能同时有学生。
判断能否让所有学生最终站在有计算机的房间中;若能,输出至多 次操作。无须最小化操作数。
输入格式
第一行一个整数 ,表示测试组数。
每组先输入一个整数 ,随后 行给出树边端点 。再输入一个整数 。
接下来一行按严格递增顺序给出学生初始位置 ;再下一行按严格递增顺序给出计算机位置 。
输出格式
每组先输出一行 YES 或 NO。
如果输出 YES,下一行输出操作数 ,满足 。随后 行,每行两个整数 ,表示把当前位于 的学生沿走廊移动到 。
数据范围
;;;各编号在 内;输入保证树连通无环,两组位置分别满足不相邻条件,并且至少一名学生初始不在有计算机的房间中。
所有测试组的 之和不超过 。
子任务
| 子任务 | 附加限制 | 分值 |
|---|---|---|
| 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