题目描述

Farmer John 和 Farmer Nhoj 把各自的奶牛带到篝火旁，希望能解决他们之间的个人分歧。总共有 $N$ ($2 \leq N \leq 10^5$) 头奶牛围成一个圆圈坐着。当农场主准备带奶牛回农场时，他们意识到一个严重的问题：由于所有奶牛看起来都一样且混在一起，他们无法辨认哪些奶牛属于哪位农场主！

随后，这 $N$ 头奶牛被排成一条直线，以便两位农场主进行询问。由于混乱，奶牛在直线上的顺序（从 $1$ 到 $N$）可能与它们在篝火旁的圆圈顺序并不对应。

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

给定奶牛们的陈述，是否可能为每头奶牛分配一位农场主（Farmer John 或 Farmer Nhoj），使得分配给 Farmer John 的奶牛的陈述全部为真，而分配给 Farmer Nhoj 的奶牛的陈述全部为假？

输入格式

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

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

下一行包含一个长度为 $N$ 的字符串，由字符 J 或 N 组成。如果第 $i$ 头奶牛声称圆圈中它左侧的奶牛属于 Farmer John，则第 $i$ 个字符为 J，否则为 N。

下一行包含一个长度为 $N$ 的字符串，由字符 J 或 N 组成。如果第 $i$ 头奶牛声称圆圈中它右侧的奶牛属于 Farmer John，则第 $i$ 个字符为 J，否则为 N。

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

输出格式

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

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

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

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

任何合法的构造方案均可被接受。

样例

样例输入 1

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

样例输出 1

YES
NO
NO
YES
NO
YES

样例输入 2

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

样例输出 2

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 属于 Farmer John，奶牛 3 属于 Farmer Nhoj。

奶牛们的行为如下：

• 奶牛 1 的左邻居是奶牛 2，右邻居是奶牛 3。奶牛 1 声称奶牛 2 属于 Farmer John，奶牛 3 属于 Farmer Nhoj。
• 奶牛 2 的左邻居是奶牛 5，右邻居是奶牛 1。奶牛 2 声称两头奶牛都属于 Farmer John。
• 奶牛 3 的左邻居是奶牛 1，右邻居是奶牛 4。奶牛 3（撒谎）声称两头奶牛都属于 Farmer Nhoj。
• 奶牛 4 的左邻居是奶牛 3，右邻居是奶牛 5。奶牛 4 声称奶牛 3 属于 Farmer Nhoj，奶牛 5 属于 Farmer John。
• 奶牛 5 的左邻居是奶牛 4，右邻居是奶牛 2。奶牛 5 声称两头奶牛都属于 Farmer John。

所有这些陈述均与输入一致。

子任务

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