#P18055. Organize the Bookshelf

Organize the Bookshelf

Organize the Bookshelf

给定两个长度为 nn 的整数序列 a,ba,b。你可以执行以下操作:选择 1≤i,j≤n1\le i,j\le n,交换 aia_i 和 bjb_j,代价为 ∣i−j∣|i-j|。

请使两个序列对应位置的数全部相等,并使总代价最小。输出的操作次数不能超过 3n3n;可以证明,只要有解,就存在不超过 3n3n 次操作的最优方案。

输入格式

第一行一个整数 TT,1≤T≤2×1051\le T\le2\times10^5。每个用例包含:

  • 一行一个整数 nn,1≤n≤2×1051\le n\le2\times10^5。
  • 一行 nn 个整数 a1,…,ana_1,\ldots,a_n。
  • 一行 nn 个整数 b1,…,bnb_1,\ldots,b_n。

所有 ai,bia_i,b_i 均在 [1,n][1,n] 内。所有用例的 nn 之和不超过 2×1052\times10^5。

输出格式

若无解,输出一行 −1-1。

否则第一行输出两个整数 cost num,分别是最小总代价和操作次数,要求 0≤num≤3n0\le\text{num}\le3n。随后输出 num 行,每行两个整数 i,ji,j,表示交换当前的 ai,bja_i,b_j。

允许输出任意最优方案。注意 i=ji=j 的交换是合法的,代价为 00。

样例

输入:

3
3
1 1 3
3 2 2
4
1 2 2 3
4 4 3 1
2
1 1
2 1

输出(一种合法答案):

2 2
2 1
3 2
3 4
1 2
3 2
4 4
4 3
-1