Universal Cup Judging System

Universal Cup

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

On vous donne deux permutations $p$ et $q$ de longueur $n$. Vous pouvez effectuer l'opération suivante sur la première permutation zéro ou plusieurs fois :

Choisir $1 \le i < j \le n$ tels que $p_i < p_j$ et échanger $p_i$ avec $p_j$.

Vous devez déterminer s'il est possible de rendre $p$ égale à $q$. Si c'est possible, vous devez trouver n'importe quelle suite d'opérations convenable.

Entrée

Chaque test contient plusieurs cas de test. La première ligne contient le nombre de cas de test $t$ ($1 \le t \le 100$). La description des cas de test suit.

La première ligne de chaque cas de test contient un entier $n$ ($1 \le n \le 2000$).

La deuxième ligne contient $n$ entiers distincts $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$).

La troisième ligne contient $n$ entiers distincts $q_1, q_2, \dots, q_n$ ($1 \le q_i \le n$).

Les suites $p$ et $q$ données sont toutes deux des permutations de $\{1, 2, \dots, n\}$.

La somme de $n$ sur l'ensemble des cas de test ne dépasse pas $2000$.

Sortie

Pour chaque cas de test, déterminez s'il existe un moyen de rendre $p$ égale à $q$.

Si c'est le cas, affichez YES sur la première ligne. Sur la ligne suivante, affichez un entier $k$, le nombre d'opérations que vous souhaitez effectuer. Sur les lignes suivantes, vous devez afficher les opérations.

Pour décrire une opération qui échange $p_i$ avec $p_j$ ($1 \le i < j \le n$), affichez une ligne formatée sous la forme « $i\ j$ ».

Sinon, affichez NO sur une seule ligne.

S'il existe plusieurs réponses convenables, affichez n'importe laquelle d'entre elles.

Exemples

Entrée 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

Sortie 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

Remarque

Dans le deuxième cas de test, $p$ vaut 1 2 3. L'une des suites d'échanges possibles est : 1 2, 1 3, 2 3.

Après le premier échange, $p$ devient 2 1 3 ; après le deuxième échange, elle devient 3 1 2 ; et après le troisième, 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.