Farmer John và Farmer Nhoj đưa những chú bò của mỗi người đến ngồi quanh một đống lửa trại với hy vọng giải quyết những bất đồng cá nhân. Tổng cộng có \(N\) (\(2 \leq N \leq 10^5\)) chú bò ngồi thành một vòng tròn. Khi hai người nông dân chuẩn bị đưa bò về trang trại của mình, họ nhận ra một sai lầm nghiêm trọng: vì tất cả các chú bò trông giống hệt nhau và đang ngồi lẫn lộn, họ không thể xác định chú bò nào thuộc về người nào!

Sau đó, \(N\) chú bò được xếp thành một hàng thẳng để hai người nông dân thẩm vấn. Do sự hỗn loạn, thứ tự các chú bò trong hàng, từ \(1\) đến \(N\), có thể không tương ứng với thứ tự của chúng trên vòng tròn quanh đống lửa trại.

Tuy nhiên, những chú bò muốn chơi một trò chơi. Thay vì trả lời trực tiếp mình thuộc về người nông dân nào, mỗi chú bò cho biết những chú bò kề với mình trên vòng tròn ban đầu thuộc về người nông dân nào. Ngoài ra, ta biết rằng bò của Farmer Nhoj luôn nói dối, còn Farmer John đã nuôi dạy bò của mình rất tốt nên chúng luôn nói thật.

Cho các lời khai của những chú bò, liệu có thể gán mỗi chú bò cho Farmer John hoặc Farmer Nhoj sao cho mọi lời khai của những chú bò được gán cho Farmer John đều đúng, còn mọi lời khai của những chú bò được gán cho Farmer Nhoj đều sai hay không?

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1 \leq T \leq 1000\)), số lượng bộ test độc lập, và một số nguyên \(C\in\{0,1\}\) (cho biết có cần in ra một cách xây dựng hay không).

Dòng đầu tiên của mỗi bộ test chứa \(N\).

Dòng tiếp theo chứa một xâu độ dài \(N\) chỉ gồm các ký tự J hoặc N. Ký tự thứ \(i\) là J nếu bò \(i\) khẳng định rằng chú bò ở bên trái mình trên vòng tròn thuộc về Farmer John; nếu không, ký tự đó là N, tức chú bò ấy khẳng định rằng chú bò bên trái thuộc về Farmer Nhoj.

Dòng tiếp theo chứa một xâu độ dài \(N\) chỉ gồm các ký tự J hoặc N. Ký tự thứ \(i\) là J nếu bò \(i\) khẳng định rằng chú bò ở bên phải mình trên vòng tròn thuộc về Farmer John; nếu không, ký tự đó là N, tức chú bò ấy khẳng định rằng chú bò bên phải thuộc về Farmer Nhoj.

Đảm bảo tổng \(N\) trên tất cả các bộ test không vượt quá \(5\cdot 10^5\).

Dữ liệu ra

Với mỗi bộ test, in ra YES hoặc NO.

Ngoài ra, nếu \(C=1\) và đáp án là YES, hãy in thêm hai dòng mô tả cách xây dựng của bạn:

Dòng đầu tiên chứa một hoán vị \(p_1,p_2,\dots,p_N\) của \(1\dots N\), biểu diễn thứ tự vòng tròn của những chú bò quanh đống lửa trại, trong đó bò \(p_i\) nằm bên trái bò \(p_{i+1}\) với mọi \(i\) từ \(1\) đến \(N-1\), và bò \(p_N\) nằm bên trái bò \(p_1\).

Dòng thứ hai chứa một xâu \(b_1b_2\dots b_N\) chỉ gồm các ký tự J và N, có nghĩa là bò \(p_i\) thuộc về Farmer John nếu \(b_i\) là J, hoặc thuộc về Farmer Nhoj nếu không.

Bất kỳ cách xây dựng hợp lệ nào cũng được chấp nhận.

Ví dụ

6 0
3
JJJ
JJJ
4
JJNJ
NJJJ
6
NJNJNJ
JNNJNJ
4
NNNN
NNNN
3
NNN
NNN
5
JJNNJ
NJNJJ

YES
NO
NO
YES
NO
YES

6 1
3
JJJ
JJJ
4
JJNJ
NJJJ
6
NJNJNJ
JNNJNJ
4
NNNN
NNNN
3
NNN
NNN
5
JJNNJ
NJNJJ

YES
1 2 3
JJJ
NO
NO
YES
1 2 3 4
NJNJ
NO
YES
4 5 2 1 3
JJJJN

Phân nhóm

• Input 3: \(C=0\) và \(N\le 10\).
• Input 4: \(C=1\) và \(N\le 10\).
• Inputs 5–8: \(C=0\).
• Inputs 9–12: \(C=1\).

Nguồn

USACO 2026 Contest 2, Silver — Cow-libi 2. Tác giả: Chongtian Ma.

https://usaco.org/index.php?page=viewproblem2&cpid=1566