#P17897. Two Permutations
Two Permutations
题目描述
给定两个长度为 的排列 。排列包含 到 的每个整数各一次。
你可以对 执行任意次以下操作,也可以一次都不执行:
选择两个位置 ,满足 且当前 ,交换 与 。
判断能否将 变为 。如果可以,请输出一种操作序列,操作次数不得超过 。
输入格式
第一行包含整数 ,表示测试用例数。
每个测试用例包含三行:第一行为 ;第二行为排列 ;第三行为排列 。
输出格式
对每个测试用例:
- 如果无法完成变换,输出一行
NO。 - 否则,先输出一行
YES;再输出一行整数 ,表示操作次数,要求 ;随后输出 行,每行两个整数 ,描述一次操作。
操作必须按输出顺序执行,每一次都必须满足当时的 和 。执行完所有操作后,排列必须等于 。
如果有多种合法答案,输出任意一种。
数据范围
- ;
- ;
- 都是 到 的排列;
- 一个输入文件内所有测试用例的 之和不超过 。
样例输入
2
3
1 2 3
3 2 1
3
3 2 1
1 2 3
样例输出
YES
1
1 3
NO
样例解释
第一个测试用例中,可以交换位置 与 。第二个测试用例的初始排列中不存在上升对,因此无法进行任何操作。
来源
The 4th Universal Cup. Stage 3: Polar Grand Prix,Two Permutations。