Universal Cup Judging System

Universal Cup

実行時間制限: 1.0 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

Du får två permutationer $p$ och $q$ av längd $n$. Du kan utföra följande operation på den första permutationen noll eller fler gånger:

Välj $1 \le i < j \le n$ sådana att $p_i < p_j$ och byt plats på $p_i$ och $p_j$.

Du behöver avgöra om det är möjligt att göra $p$ lika med $q$. Om det är möjligt behöver du hitta en lämplig sekvens av operationer.

Indata

Varje test innehåller flera testfall. Den första raden innehåller antalet testfall $t$ ($1 \le t \le 100$). Beskrivningen av testfallen följer.

Den första raden i varje testfall innehåller ett heltal $n$ ($1 \le n \le 2000$).

Den andra raden innehåller $n$ olika heltal $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$).

Den tredje raden innehåller $n$ olika heltal $q_1, q_2, \dots, q_n$ ($1 \le q_i \le n$).

De givna $p$ och $q$ är båda permutationer av $\{1, 2, \dots, n\}$.

Summan av $n$ över alla testfall överstiger inte $2000$.

Utdata

För varje testfall, avgör om det finns ett sätt att göra $p$ lika med $q$.

Om så är fallet, skriv ut YES på den första raden. På nästa rad, skriv ut ett heltal $k$, antalet operationer du vill utföra. På de följande raderna ska du skriva ut operationerna.

För att beskriva en operation som byter plats på $p_i$ och $p_j$ ($1 \le i < j \le n$), skriv ut en rad formaterad som "$i\ j$".

Annars, skriv ut NO på en ensam rad.

Om det finns flera lämpliga svar, skriv ut vilket som helst av dem.

Exempel

Indata 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

Utdata 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

Förklaring

I det andra testfallet är $p$ lika med 1 2 3. En av de möjliga sekvenserna av byten är: 1 2, 1 3, 2 3.

Efter det första bytet blir $p$ lika med 2 1 3; efter det andra bytet blir den 3 1 2; och efter det tredje, 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.