← 返回题目列表

Codeforces · 1243/B2

B2. 角色交换(困难版)

中文机器翻译题面 查看原题

这个问题与简单版本不同。在此版本中,Ujan 最多进行 $$$2n$$$ 交换。此外,$$$k \le 1000,n \le 50$$$ 并且有必要自己打印掉期。如果你解决了这个问题,你就可以破解它。但只有解决了这两个问题,才能破解前一个问题。

在多次挣扎和失败之后,Ujan决定再次尝试清理他的房子。他决定先把琴弦整理好。

Ujan 有两个不同的字符串 $$$s$$$ 和 $$$t$$$,长度为 $$$n$$$,仅由小写英文字符组成。他想让他们平等。由于Ujan是懒惰的,他最多会执行$$$2n$$$次:他占据两个位置$$$i$$$和$$$j$$$($$$1 \le i,j \le 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”。您可以以任何大小写(大写或小写)打印每个字母。

如果选择“是”,则在下一行打印 $$$m$$$ ($$$1 \le m \le 2n$$$),其中 $$$m$$$ 是使字符串相等的交换操作数。然后打印 $$$m$$$ 行,每行应包含两个整数 $$$i, j$$$ ($$$1 \le i, j \le n$$$) 意味着 Ujan 在相应操作期间交换 $$$s_i$$$ 和 $$$t_j$$$。您不需要最小化操作数量。任何长度不超过 $$$2n$$$ 的序列都是合适的。

示例

输入 #1

4
5
souse
houhe
3
cat
dog
2
aa
az
3
abc
bca

输出 #1

Yes
1
1 4
No
No
Yes
3
1 2
3 1
2 3