Universal Cup Judging System

Universal Cup

حد الوقت: 1.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

畀你兩個長度為 $n$ 嘅排列 $p$ 同 $q$。你可以對第一個排列進行零次或者多次以下操作:

揀 $1 \le i < j \le n$ 令到 $p_i < p_j$,然後交換 $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.