Problem Description

cyq works as a PE teacher at tsyz and is responsible for lining students up.

In tsyz, each person has a height $a_i$, and only two adjacent people are allowed to swap positions. The team led by cyq has $n$ people, and he now wants to arrange them into a formation.

Given a sequence $b$ of length $n$, a formation is considered beautiful if and only if for all $i = 1, 2, 3, \dots n$, $a_i = b_i$. cyq wants to know whether he can make the formation beautiful, and the number of adjacent swaps does not exceed $n^2$. This problem has stumped $cyq$. Please help solve it: if there exists a valid swapping plan, output YES and provide one plan; otherwise, output NO.

Input Format

This problem contains multiple test cases within a single test point.

The first line contains an integer $T$, indicating the number of test cases. For each test case:
The first line contains an integer, representing the team length $n$.
The second line contains $n$ integers; the $i$-th integer is the height $a_i$ of the $i$-th person.
The third line contains $n$ integers; the $i$-th integer is the height $b_i$ of the $i$-th person in the beautiful formation.

Output Format

For each test case, output the answer in order.

For each test case, if there exists a plan, output YES on the first line; otherwise, output NO.

If you output YES, then output several lines, each containing two integers $i, j$, meaning that the $i$-th student and the $j$-th student swap positions. Obviously, $|i - j| = 1$. After finishing all swaps, you must output one line 0 0 to indicate the end of your operations. Note that the array indices are numbered from 1 to $n$.

If you output NO, then you do not need to output anything afterward.

Please pay special attention: for each test case, the number of operations must not exceed $n^2$ (not including the line 0 0), otherwise you will get WA (Wrong Answer).

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

YES
4 3
2 3
1 2
3 2
3 4
0 0
NO
YES
0 0

Hint

Constraints

For all test points, it is guaranteed that $1 \le T \le 10$, $1 \le n \le 10^3$, $1 \le a_i, b_i \le 10^9$, and the sum of $n$ over all test cases does not exceed $1000$, i.e. $\sum n \le 10^3$.

Notes

• Please note that a large amount of output may affect program efficiency, so do not flush the buffer too often. For example, C++ users using std::cout should use '\n' instead of std::endl for newlines; Java users should choose efficient output methods such as using PrintWriter; Python users can use print normally without worrying about efficiency.
• Please output your answer according to the required output format. If the format is incorrect, the judging feedback may be TLE, RE, WA, UKE, or any other result.

Example of efficient output in C++

#include <iostream>
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  for (int i = 1; i <= 5; ++i) {
    std::cout << i << '\n'; // Note that std::endl cannot be used here
  }
}

Example of efficient output in Java

import java.io.PrintWriter;

public class Main {
  public static void main(String[] args) {
    PrintWriter ot = new PrintWriter(System.out);
    for (int i = 1; i <= 5; ++i) {
      ot.println(i);
    }
    ot.flush(); // Make sure to run this line when the program ends, otherwise the buffer content cannot be output
  }
}

Translated by ChatGPT 5