Universal Cup Judging System

Universal Cup

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

長さ $n$ の 2 つの順列 $p$ と $q$ が与えられます。1 つ目の順列に対して、以下の操作を 0 回以上行うことができます:

$p_i < p_j$ を満たす $1 \le i < j \le n$ を選び、$p_i$ と $p_j$ を入れ替える。

$p$ を $q$ に一致させることが可能かどうかを判定してください。可能な場合は、条件を満たす操作列を 1 つ求めてください。

入力

各テストは複数のテストケースを含みます。1 行目にはテストケースの個数 $t$($1 \le t \le 100$)が与えられます。続いて各テストケースの記述が与えられます。

各テストケースの 1 行目には整数 $n$($1 \le n \le 2000$)が与えられます。

2 行目には $n$ 個の相異なる整数 $p_1, p_2, \dots, p_n$($1 \le p_i \le n$)が与えられます。

3 行目には $n$ 個の相異なる整数 $q_1, q_2, \dots, q_n$($1 \le q_i \le n$)が与えられます。

与えられる $p$ と $q$ はどちらも $\{1, 2, \dots, n\}$ の順列です。

すべてのテストケースにおける $n$ の総和は $2000$ を超えません。

出力

各テストケースについて、$p$ を $q$ に一致させる方法が存在するかどうかを判定してください。

存在する場合は、1 行目に YES を出力してください。次の行には、実行したい操作の回数を表す整数 $k$ を出力してください。続く行には、各操作を出力してください。

$p_i$ と $p_j$($1 \le i < j \le n$)を入れ替える操作を表すには、「$i\ j$」という形式の行を出力してください。

存在しない場合は、1 行に 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

注記

2 番目のテストケースでは、$p$ は 1 2 3 です。可能な入れ替え操作の列の 1 つは、1 2、1 3、2 3 です。

1 回目の入れ替えの後、$p$ は 2 1 3 になり、2 回目の入れ替えの後は 3 1 2 になり、3 回目の後は 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.