Cow-libi 2

$N$ con bò ngồi quanh đống lửa trại thành một vòng tròn. Mỗi con bò thuộc về bác John hoặc bác Nhoj: bò của bác John luôn nói thật, còn bò của bác Nhoj luôn nói dối.

Từng con bò được thẩm vấn riêng. Con bò thứ $i$ khai hai điều:

• $l_i$: chủ của con bò ngồi ngay bên trái nó ($l_i$ là J nếu nó khai đó là bò của bác John, là N nếu nó khai đó là bò của bác Nhoj).
• $r_i$: chủ của con bò ngồi ngay bên phải nó, quy ước tương tự.

Bò của bác John khai đúng chủ của hai con bò bên cạnh. Bò của bác Nhoj khai sai cả hai, nghĩa là nó luôn nói ngược lại chủ thật sự của con bò bên cạnh.

Hãy cho biết có tồn tại cách xếp $N$ con bò thành vòng tròn và gán chủ cho từng con sao cho mọi lời khai đều đúng với quy tắc trên hay không, và nếu có thì chỉ ra một cách.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $T$ và $C$, là số bộ dữ liệu và chế độ xuất kết quả.
• Mỗi bộ dữ liệu gồm ba dòng:
  • Dòng 1: số nguyên $N$.
  • Dòng 2: xâu $l_1{l}_2\dots l_N$ gồm $N$ ký tự J hoặc N.
  • Dòng 3: xâu $r_1{r}_2\dots r_N$ gồm $N$ ký tự J hoặc N.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra YES nếu tồn tại cách xếp thoả mãn, ngược lại in ra NO.

Nếu $C=1$ và câu trả lời là YES, in thêm hai dòng:

• Dòng thứ nhất: hoán vị $p_1,p_2,\dots ,p_N$ của $1,2,\dots ,N$ mô tả vòng tròn, trong đó bò $p_{i+1}$ ngồi ngay bên phải bò $p_i$ với mọi $i<N$, còn bò $p_1$ ngồi ngay bên phải bò $p_N$.
• Dòng thứ hai: xâu $b_1{b}_2\dots b_N$ gồm $N$ ký tự, với $b_i$ là J nếu bò $i$ thuộc về bác John và là N nếu bò $i$ thuộc về bác Nhoj.

Nếu có nhiều cách xếp thoả mãn, in ra một cách bất kỳ.

Ràng buộc

• $1\le T\le 1000$
• $C\in \{0,1\}$
• $2\le N\le {10}^5$
• Tổng $N$ trên tất cả các bộ dữ liệu không vượt quá $5\times {10}^5$

Ví dụ