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.