Universal Cup Judging System

Universal Cup

Time Limit: 1.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

길이가 $n$인 두 순열 $p$와 $q$가 주어집니다. 첫 번째 순열에 대해 다음 연산을 0번 이상 수행할 수 있습니다:

$p_i < p_j$를 만족하는 $1 \le i < j \le n$을 선택하고, $p_i$와 $p_j$를 교환합니다.

$p$를 $q$와 같게 만들 수 있는지 판별해야 합니다. 만약 가능하다면, 조건을 만족하는 임의의 연산 수열을 찾아야 합니다.

입력

각 테스트는 여러 개의 테스트 케이스를 포함합니다. 첫 번째 줄에는 테스트 케이스의 개수 $t$($1 \le t \le 100$)가 주어집니다. 이어서 테스트 케이스들의 설명이 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 정수 $n$($1 \le n \le 2000$)이 주어집니다.

두 번째 줄에는 $n$개의 서로 다른 정수 $p_1, p_2, \dots, p_n$($1 \le p_i \le n$)이 주어집니다.

세 번째 줄에는 $n$개의 서로 다른 정수 $q_1, q_2, \dots, q_n$($1 \le q_i \le n$)이 주어집니다.

주어지는 $p$와 $q$는 모두 $\{1, 2, \dots, n\}$의 순열입니다.

모든 테스트 케이스에서 $n$의 합은 $2000$을 넘지 않습니다.

출력

각 테스트 케이스에 대해, $p$를 $q$와 같게 만드는 방법이 존재하는지 판별하세요.

만약 존재한다면, 첫 번째 줄에 YES를 출력합니다. 다음 줄에는 수행하고자 하는 연산의 횟수를 나타내는 정수 $k$를 출력합니다. 그다음 줄들에는 수행할 연산들을 출력해야 합니다.

$p_i$와 $p_j$($1 \le i < j \le n$)를 교환하는 연산을 설명하려면 "$i\ j$" 형식의 줄을 출력합니다.

그렇지 않다면, 한 줄에 NO를 출력합니다.

적절한 답이 여러 개 있는 경우, 그중 아무것이나 하나를 출력합니다.

예제

입력 1

6
2
1 2
2 1
3
1 2 3
3 2 1
5
3 5 1 2 4
4 5 1 3 2
6
2 3 6 4 1 5
3 4 5 6 2 1
6
2 3 6 4 1 5
5 3 6 4 2 1
1
1
1

출력 1

YES
1
1 2
YES
3
1 2
1 3
2 3
YES
2
1 5
4 5
NO
YES
6
1 2
1 4
1 6
2 4
4 6
5 6
YES
0

참고

두 번째 테스트 케이스에서 $p$는 1 2 3입니다. 가능한 교환 수열 중 하나는 1 2, 1 3, 2 3입니다.

첫 번째 교환 후 $p$는 2 1 3이 되고, 두 번째 교환 후에는 3 1 2가 되며, 세 번째 교환 후에는 3 2 1이 됩니다.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.