Farmer John and Farmer Nhoj have taken their respective cows to sit around a campfire in hopes of settling their personal differences. In total, there are N
(2≤N≤105) cows sitting in a circular formation. When the farmers are ready to take their cows back to their farms, they realize one crucial mistake: since all the cows look the same and are mixed up, they are unable to identify which cows belong to which farmer!
Then the N cows are organized into one straight line to be interrogated by the two farmers. Because of the confusion, the order of the cows in the line, from 1
to N, might not correspond to their circular order around the campfire.
But the cows want to play a game. Instead of answering directly which farmer they belong to, they say which farmer the cows adjacent to them in the original circle belong to. Additionally, it is known that Farmer Nhoj's cows always lie but Farmer John raised his cows well and they will always tell the truth.
Given the statements of the cows, is it possible to assign each cow to either Farmer John or Farmer Nhoj such that the statements of the cows assigned to Farmer John are all true, and the statements of the cows assigned to Farmer Nhoj are all false?
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains T (1≤T≤1000), the number of independent test cases, and an integer C∈{0,1} (whether to output a construction or not).
The first line of each test case contains N.
The following line contains a string of length N containing characters J or N. The i'th character is J if cow i claims the cow to their left in the circle belongs to Farmer John, or Farmer Nhoj otherwise.
The following line contains a string of length N containing characters J or N. The i'th character is J if cow i claims the cow to their right in the circle belongs to Farmer John, or Farmer Nhoj otherwise.
It is guaranteed that the sum of N over all tests does not exceed 5⋅105.
OUTPUT FORMAT (print output to the terminal / stdout):
For each test case, output YES or NO.
Additionally, if C=1 and the answer is YES, output two more lines describing your construction:
The first line should contain a permutation p1,p2,…,pN of 1…N, representing the circular order of the cows around the campfire, where cow pi is to the left of cow pi+1 for i in 1…N−1, and cow pN is to the left of cow p1.
The second line should contain a string b1b2…bN consisting only of Js and Ns, meaning that cow pi belongs to Farmer John if bi is J, or Farmer Nhoj otherwise.
Any valid construction will be accepted.
SAMPLE INPUT:
6 0
3
JJJ
JJJ
4
JJNJ
NJJJ
6
NJNJNJ
JNNJNJ
4
NNNN
NNNN
3
NNN
NNN
5
JJNNJ
NJNJJ
SAMPLE OUTPUT:
YES
NO
NO
YES
NO
YES
SAMPLE INPUT:
6 1
3
JJJ
JJJ
4
JJNJ
NJJJ
6
NJNJNJ
JNNJNJ
4
NNNN
NNNN
3
NNN
NNN
5
JJNNJ
NJNJJ
SAMPLE OUTPUT:
YES
1 2 3
JJJ
NO
NO
YES
1 2 3 4
NJNJ
NO
YES
4 5 2 1 3
JJJJN
Consider the output for the sixth test case. Cows 1, 2, 4, 5 belong to Farmer John, and Cow 3 belongs to Farmer Nhoj.
The cows will then behave as follows:
Cow 1's left and right neighbours are Cow 2 and Cow 3, respectively. Cow 1 says that Cow 2 belongs to Farmer John, and Cow 3 belongs to Farmer Nhoj.
Cow 2's left and right neighbours are Cow 5 and Cow 1, respectively. Cow 2 says that both cows belong to Farmer John.
Cow 3's left and right neighbours are Cow 1 and Cow 4, respectively. Cow 3 (dishonestly) says that both cows belong to Farmer Nhoj.
Cow 4's left and right neighbours are Cow 3 and Cow 5, respectively. Cow 4 says that Cow 3 belongs to Farmer Nhoj, and Cow 5 belongs to Farmer John.
Cow 5's left and right neighbours are Cow 4 and Cow 2, respectively. Cow 5 says that both cows belong to Farmer John.
All these claims are consistent with the input.
SCORING:
Input 3: C=0 and N≤10
Input 4: C=1 and N≤10
Inputs 5-8: C=0
Inputs 9-12: C=1
Problem credits: Chongtian Ma