Universal Cup Judging System

Universal Cup

Limite de temps : 1.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

Bạn được cho hai hoán vị $p$ và $q$ có độ dài $n$. Bạn có thể thực hiện thao tác sau với hoán vị thứ nhất không hoặc nhiều lần:

Chọn $1 \le i < j \le n$ sao cho $p_i < p_j$ và hoán đổi $p_i$ với $p_j$.

Bạn cần xác định xem có thể biến đổi $p$ thành bằng $q$ hay không. Nếu có thể, bạn cần tìm một dãy thao tác phù hợp bất kỳ.

Dữ liệu vào

Mỗi test chứa nhiều bộ dữ liệu. Dòng đầu tiên chứa số lượng bộ dữ liệu $t$ ($1 \le t \le 100$). Mô tả của các bộ dữ liệu theo sau.

Dòng đầu tiên của mỗi bộ dữ liệu chứa một số nguyên $n$ ($1 \le n \le 2000$).

Dòng thứ hai chứa $n$ số nguyên khác nhau $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$).

Dòng thứ ba chứa $n$ số nguyên khác nhau $q_1, q_2, \dots, q_n$ ($1 \le q_i \le n$).

$p$ và $q$ đã cho đều là các hoán vị của $\{1, 2, \dots, n\}$.

Tổng của $n$ trong tất cả các bộ dữ liệu không vượt quá $2000$.

Dữ liệu ra

Với mỗi bộ dữ liệu, hãy xác định xem có tồn tại cách biến đổi $p$ thành bằng $q$ hay không.

Nếu có, hãy in ra YES trên dòng đầu tiên. Trên dòng tiếp theo, in ra một số nguyên $k$, là số lượng thao tác bạn muốn thực hiện. Trên các dòng tiếp theo, bạn cần in ra các thao tác đó.

Để mô tả một thao tác hoán đổi $p_i$ với $p_j$ ($1 \le i < j \le n$), hãy in ra một dòng có định dạng "$i\ j$".

Ngược lại, hãy in ra NO trên một dòng duy nhất.

Trong trường hợp có nhiều đáp án phù hợp, hãy in ra bất kỳ đáp án nào trong số đó.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 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

Ghi chú

Trong bộ dữ liệu thứ hai, $p$ là 1 2 3. Một trong những dãy hoán đổi khả dĩ là: 1 2, 1 3, 2 3.

Sau lần hoán đổi thứ nhất, $p$ trở thành 2 1 3; sau lần hoán đổi thứ hai, nó trở thành 3 1 2; và sau lần thứ ba, 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.