Cow-libi 2

• $N$ con bò ngồi quanh đống lửa trại theo vòng tròn. Mỗi con bò thuộc về bác John (J) hoặc bác Nhoj (N). 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.

Các con bò được xếp hàng để thẩm vấn. Mỗi con bò thứ $i$ khai báo:

• Bò bên trái mình trong vòng tròn thuộc về bác nào ($l_i$: J hoặc N).
• Bò bên phải mình trong vòng tròn thuộc về bác nào ($r_i$: J hoặc N).

Hãy xác định xem có tồn tại cách sắp xếp vòng tròn và gán bác (J/N) cho mỗi con bò sao cho tất cả các khai báo đều nhất quán hay không.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $T$ ($1\le T\le 1000$) và $C$ ($C\in \{0,1\}$).
• Với mỗi test case:
  • Dòng 1: Số nguyên $N$ ($2\le N\le {10}^5$).
  • Dòng 2: Chuỗi $l_1{l}_2\dots l_N$ gồm $N$ ký tự J hoặc N (khai báo về bò bên trái).
  • Dòng 3: Chuỗi $r_1{r}_2\dots r_N$ gồm $N$ ký tự J hoặc N (khai báo về bò bên phải).

Tổng $N$ trên tất cả test case không vượt quá $5\times {10}^5$.

Dữ liệu ra

Với mỗi test case:

• In YES hoặc NO.
• Nếu $C=1$ và đáp án là YES, in thêm hai dòng:
  • Hoán vị $p_1,p_2,\dots ,p_N$ thể hiện thứ tự ngồi quanh vòng tròn.
  • Chuỗi $b_1{b}_2\dots b_N$ gồm $N$ ký tự J hoặc N thể hiện bác mà mỗi con bò thuộc về.

Ràng buộc

• $1\le T\le 1000$
• $2\le N\le {10}^5$
• Tổng $N\le 5\times {10}^5$
• Input 3: $C=0$, $N\le 10$
• Input 4: $C=1$, $N\le 10$

Ví dụ