说明

农夫 John 和农夫 Nhoj 带着他们各自的奶牛围坐在篝火旁，希望解决他们之间的个人分歧。总共有 $N$（$2 \leq N \leq 10^5$）头奶牛围成一个圆圈。当两位农夫准备将他们的奶牛带回农场时，他们意识到一个关键的错误：由于所有奶牛看起来都一样且混在一起，他们无法区分哪些奶牛属于哪位农夫！

随后，这 $N$ 头奶牛被组织成一列直线，接受两位农夫的询问。由于混乱，队伍中奶牛从 $1$ 到 $N$ 的顺序可能并不对应它们在篝火旁的环形顺序。

但奶牛们想玩一个游戏。它们不直接回答属于哪位农夫，而是说出在原始圆圈中与自己相邻的奶牛属于哪位农夫。此外，已知农夫 Nhoj 的奶牛总是说谎，而农夫 John 的奶牛被教养得很好，总是说实话。

根据奶牛的陈述，是否可能为每头奶牛分配属于农夫 John 或农夫 Nhoj，使得分配给农夫 John 的奶牛的所有陈述都为真，而分配给农夫 Nhoj 的奶牛的所有陈述都为假？

输入格式

第一行包含 $T$（$1 \leq T \leq 1000$），表示独立测试用例的数量，以及一个整数 $C \in \{0,1\}$（表示是否需要输出构造方案）。

每个测试用例的第一行包含 $N$。

接下来一行包含一个长度为 $N$ 的字符串，由字符 J 或 N 组成。第 $i$ 个字符为 J，表示奶牛 $i$ 声称在圆圈中其左侧的奶牛属于农夫 John；否则为 N，表示属于农夫 Nhoj。

接下来一行包含一个长度为 $N$ 的字符串，由字符 J 或 N 组成。第 $i$ 个字符为 J，表示奶牛 $i$ 声称在圆圈中其右侧的奶牛属于农夫 John；否则为 N，表示属于农夫 Nhoj。

保证所有测试用例的 $N$ 之和不超过 $5 \cdot 10^5$。

输出格式

对于每个测试用例，输出 YES 或 NO。

此外，如果 $C=1$ 且答案为 YES，则额外输出两行描述你的构造方案：

第一行应包含 $1 \dots N$ 的一个排列 $p_1, p_2, \dots, p_N$，表示奶牛在篝火旁的环形顺序，其中对于 $i$ 从 $1$ 到 $N-1$，奶牛 $p_i$ 位于奶牛 $p_{i+1}$ 的左侧，且奶牛 $p_N$ 位于奶牛 $p_1$ 的左侧。

第二行应包含一个仅由 J 和 N 组成的字符串 $b_1b_2\dots b_N$，表示如果 $b_i$ 是 J，则奶牛 $p_i$ 属于农夫 John；否则属于农夫 Nhoj。

任何有效的构造方案都将被接受。

6 0
3
JJJ
JJJ
4
JJNJ
NJJJ
6
NJNJNJ
JNNJNJ
4
NNNN
NNNN
3
NNN
NNN
5
JJNNJ
NJNJJ

YES
NO
NO
YES
NO
YES

6 1
3
JJJ
JJJ
4
JJNJ
NJJJ
6
NJNJNJ
JNNJNJ
4
NNNN
NNNN
3
NNN
NNN
5
JJNNJ
NJNJJ

YES
1 2 3
JJJ
NO
NO
YES
1 2 3 4
NJNJ
NO
YES
4 5 2 1 3
JJJJN

提示

考虑第六个测试用例的输出。奶牛 1、2、4、5 属于农夫 John，奶牛 3 属于农夫 Nhoj。

随后奶牛们的行为如下：

• 奶牛 1 的左侧和右侧邻居分别是奶牛 2 和奶牛 3。奶牛 1 声称奶牛 2 属于农夫 John，奶牛 3 属于农夫 Nhoj。
• 奶牛 2 的左侧和右侧邻居分别是奶牛 5 和奶牛 1。奶牛 2 声称两头奶牛都属于农夫 John。
• 奶牛 3 的左侧和右侧邻居分别是奶牛 1 和奶牛 4。奶牛 3（不诚实地）声称两头奶牛都属于农夫 Nhoj。
• 奶牛 4 的左侧和右侧邻居分别是奶牛 3 和奶牛 5。奶牛 4 声称奶牛 3 属于农夫 Nhoj，奶牛 5 属于农夫 John。
• 奶牛 5 的左侧和右侧邻居分别是奶牛 4 和奶牛 2。奶牛 5 声称两头奶牛都属于农夫 John。

所有这些声明都与输入一致。

评分

• 输入 3：$C=0$ 且 $N \le 10$
• 输入 4：$C=1$ 且 $N \le 10$
• 输入 5-8：$C=0$
• 输入 9-12：$C=1$

翻译由 DeepSeek 完成