P15257 [USACO26JAN2] Cow-libi 2 S

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 \leq N \leq 10^5$) 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?

The first line contains $T$ ($1 \leq T \leq 1000$), the number of independent test cases, and an integer $C\in \{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 \cdot 10^5$.

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 $p_1, p_2, \dots, p_N$ of $1\dots N$, representing the circular order of the cows around the campfire, where cow $p_i$ is to the left of cow $p_{i+1}$ for $i$ in $1 \dots N - 1$, and cow $p_N$ is to the left of cow $p_1$. The second line should contain a string $b_1b_2\dots b_N$ consisting only of Js and Ns, meaning that cow $p_i$ belongs to Farmer John if $b_i$ is J, or Farmer Nhoj otherwise. Any valid construction will be accepted.

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\le 10$ - Input 4: $C=1$ and $N\le 10$ - Inputs 5-8: $C=0$ - Inputs 9-12: $C=1$