문제

우솔이와 성현이는 동아리 MT에서 부원들과 함께 캠프파이어 주변에 둘러앉아 이야기를 나누고 있다. 총 $N$ ($2 \le N \le 10^5$)명의 부원이 원형으로 둘러앉아 있다. 모임이 끝나고 부원들을 각자의 팀으로 데려가려는데, 모든 부원의 모습이 비슷해 누가 우솔이네 팀이고 누가 성현이네 팀인지 알 수 없게 되었다.

$N$명의 부원은 조사를 받기 위해 $1$번부터 $N$번까지 일렬로 줄을 섰다. 이때 줄을 선 순서는 처음에 캠프파이어 주변에 앉았던 순서와 다를 수 있다.

부원들은 자신이 어느 팀인지 직접 말하는 대신, 원래 원형으로 앉아 있었을 때 자신의 양옆에 앉았던 부원이 어느 팀 소속이었는지를 진술한다. 이때 우솔이네 팀 부원들은 항상 진실만을 말하지만, 성현이네 팀 부원들은 항상 거짓만을 말한다.

부원들의 진술이 주어졌을 때, 모든 진술이 모순되지 않도록 각 부원을 우솔이네 팀 또는 성현이네 팀에 배정하는 것이 가능한지 판별하시오.

입력

첫째 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 1\,000$)와 구성 방식 출력 여부를 나타내는 정수 $C \in \{0, 1\}$이 공백으로 구분되어 주어진다.

각 테스트 케이스의 첫째 줄에 부원 수 $N$이 주어진다.

둘째 줄에 길이 $N$인 문자열이 주어진다. $i$번째 문자가 J이면 $i$번째 부원이 원형 좌석에서 자신의 왼쪽에 앉았던 부원이 우솔이네 팀이라고 주장한 것이고, N이면 성현이네 팀이라고 주장한 것이다.

셋째 줄에 길이 $N$인 문자열이 주어진다. $i$번째 문자가 J이면 $i$번째 부원이 원형 좌석에서 자신의 오른쪽에 앉았던 부원이 우솔이네 팀이라고 주장한 것이고, N이면 성현이네 팀이라고 주장한 것이다.

모든 테스트 케이스에 대해 $N$의 합은 $5 \cdot 10^5$을 초과하지 않는다.

출력

각 테스트 케이스마다 배정이 가능하면 YES, 불가능하면 NO를 출력한다.

추가로, $C=1$이고 답이 YES인 경우에는 구성을 설명하는 두 줄을 더 출력한다.

첫 번째 줄에는 $1$부터 $N$까지의 정수가 한 번씩 등장하는 순열 $p_1, p_2, \dots, p_N$을 공백으로 구분하여 출력한다. 이는 부원들이 캠프파이어 주변에 앉았던 순서를 나타낸다. 이때 부원 $p_i$의 왼쪽에는 부원 $p_{i+1}$이 있고 ($1 \le i \le N-1$), 부원 $p_N$의 왼쪽에는 부원 $p_1$이 있어야 한다.

두 번째 줄에는 J와 N으로만 구성된 길이 $N$인 문자열 $b_1b_2\dots b_N$을 출력한다. 여기서 $b_i$는 부원 $p_i$가 우솔이네 팀이면 J, 성현이네 팀이면 N임을 의미한다.

가능한 구성이 여러 가지라면 그중 하나만 출력한다.

예제 입력 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

채점 정보

• 입력 3: $C=0, N \le 10$
• 입력 4: $C=1, N \le 10$
• 입력 5-8: $C=0$
• 입력 9-12: $C=1$