#P17897. Two Permutations

Two Permutations

题目描述

给定两个长度为 nn 的排列 p,qp,q。排列包含 11 到 nn 的每个整数各一次。

你可以对 pp 执行任意次以下操作,也可以一次都不执行:

选择两个位置 i,ji,j,满足 1≤i<j≤n1\le i<j\le n 且当前 pi<pjp_i<p_j,交换 pip_i 与 pjp_j。

判断能否将 pp 变为 qq。如果可以,请输出一种操作序列,操作次数不得超过 n2n^2。

输入格式

第一行包含整数 tt,表示测试用例数。

每个测试用例包含三行:第一行为 nn;第二行为排列 pp;第三行为排列 qq。

输出格式

对每个测试用例:

  • 如果无法完成变换,输出一行 NO。
  • 否则,先输出一行 YES;再输出一行整数 kk,表示操作次数,要求 0≤k≤n20\le k\le n^2;随后输出 kk 行,每行两个整数 i,ji,j,描述一次操作。

操作必须按输出顺序执行,每一次都必须满足当时的 i<ji<j 和 pi<pjp_i<p_j。执行完所有操作后,排列必须等于 qq。

如果有多种合法答案,输出任意一种。

数据范围

  • 1≤t≤1001\le t\le100;
  • 1≤n≤20001\le n\le2000;
  • p,qp,q 都是 11 到 nn 的排列;
  • 一个输入文件内所有测试用例的 nn 之和不超过 20002000。

样例输入

2
3
1 2 3
3 2 1
3
3 2 1
1 2 3

样例输出

YES
1
1 3
NO

样例解释

第一个测试用例中,可以交换位置 11 与 33。第二个测试用例的初始排列中不存在上升对,因此无法进行任何操作。

来源

The 4th Universal Cup. Stage 3: Polar Grand Prix,Two Permutations。