CF1243B2 Character Swap (Hard Version)

本题与简单版本不同。在本版本中，Ujan 最多可以进行 $2n$ 次交换操作。此外，$k \leq 1000$，$n \leq 50$，并且需要输出具体的交换操作。如果你解决了本题，可以对本题进行 hack。但只有同时解决了本题和前一题，才能对前一题进行 hack。 经过多次尝试和失败后，Ujan 决定再次整理他的房子。他首先决定整理好他的字符串。 Ujan 有两个长度为 $n$ 的不同字符串 $s$ 和 $t$，它们只包含小写英文字母。他希望将这两个字符串变得相同。由于 Ujan 很懒，他最多会进行 $2n$ 次如下操作：他选择两个位置 $i$ 和 $j$（$1 \leq i, j \leq n$，$i$ 和 $j$ 可以相同也可以不同），然后交换 $s_i$ 和 $t_j$ 这两个字符。 Ujan 的目标是让字符串 $s$ 和 $t$ 变得完全相同。他不需要让操作次数最少：任何长度不超过 $2n$ 的操作序列都是可以接受的。

第一行包含一个整数 $k$（$1 \leq k \leq 1000$），表示测试用例的数量。 对于每个测试用例，第一行包含一个整数 $n$（$2 \leq n \leq 50$），表示字符串 $s$ 和 $t$ 的长度。 接下来的两行分别为字符串 $s$ 和 $t$，每个字符串长度恰好为 $n$，且只包含小写英文字母。保证两个字符串不同。

对于每个测试用例，如果 Ujan 能够在不超过 $2n$ 次操作内将两个字符串变得相同，输出 "Yes"；否则输出 "No"。你可以用任意大小写输出字母。 如果输出 "Yes"，则在下一行输出一个整数 $m$（$1 \leq m \leq 2n$），表示将两个字符串变得相同所需的交换操作次数。接下来的 $m$ 行，每行输出两个整数 $i, j$（$1 \leq i, j \leq n$），表示在对应操作中 Ujan 交换 $s_i$ 和 $t_j$。你不需要让操作次数最少，任何长度不超过 $2n$ 的操作序列都是可以接受的。

由 ChatGPT 4.1 翻译