Bạn có thể đi con đường của riêng mình

Đề bài

Bạn vừa bước vào mê cung dễ nhất thế giới. Bạn bắt đầu tại ô phía tây bắc của một lưới gồm \(N \times N\) ô vuông đơn vị và phải đi đến ô phía đông nam. Bạn chỉ có thể thực hiện hai loại bước đi: đi một đơn vị về phía đông và đi một đơn vị về phía nam. Bạn có thể đi vào bất kỳ ô nào, nhưng không được thực hiện bước đi khiến bạn ra khỏi lưới.

Bạn rất hào hứng vì sắp trở thành người đầu tiên trên thế giới giải được mê cung, nhưng rồi bạn nhìn thấy những dấu chân. Đối thủ của bạn, Labyrinth Lydia, đã giải mê cung trước bạn theo đúng các quy tắc được mô tả ở trên!

Là một người có tư duy độc lập, bạn không muốn sử dụng lại bất kỳ bước đi nào của Lydia. Cụ thể, nếu đường đi của cô ấy có một bước đi đơn vị từ một ô \(A\) nào đó sang ô kề \(B\), đường đi của bạn không được chứa bước đi từ \(A\) sang \(B\). (Tuy nhiên, trong trường hợp đó, đường đi của bạn vẫn được phép ghé qua \(A\) hoặc \(B\), miễn là bạn không đi từ \(A\) sang \(B\).) Hãy tìm một đường đi như vậy.

Trong hình minh họa sau đây, đường đi của Lydia được tô màu xanh dương và một đường đi hợp lệ có thể có của bạn được tô màu cam.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Tiếp theo là \(T\) bộ test; mỗi bộ gồm hai dòng. Dòng đầu tiên chứa một số nguyên \(N\), cho biết kích thước của mê cung như đã mô tả ở trên. Dòng thứ hai chứa chuỗi \(P\) gồm \(2N - 2\) ký tự; mỗi ký tự là chữ cái in hoa E (đi về phía đông) hoặc chữ cái in hoa S (đi về phía nam), biểu diễn đường đi hợp lệ của Lydia qua mê cung.

Dữ liệu ra

Với mỗi bộ test, hãy in một dòng có dạng Case #x: y, trong đó x là số thứ tự của bộ test (bắt đầu từ \(1\)), còn y là một chuỗi gồm \(2N - 2\) ký tự; mỗi ký tự là chữ cái in hoa E (đi về phía đông) hoặc chữ cái in hoa S (đi về phía nam), biểu diễn một đường đi hợp lệ của bạn qua mê cung và không xung đột với đường đi của Lydia như đã mô tả ở trên. Đề bài đảm bảo luôn tồn tại ít nhất một đáp án.

Ràng buộc

• \(1 \le T \le 100\).
• \(P\) chứa chính xác \(N - 1\) ký tự E và chính xác \(N - 1\) ký tự S.

Phân nhóm

Test Set 1 (Hiển thị)

• \(2 \le N \le 10\).

Test Set 2 (Hiển thị)

• \(2 \le N \le 1000\).

Test Set 3 (Ẩn)

• Với nhiều nhất \(10\) bộ test, \(2 \le N \le 50000\).
• Với tất cả các bộ test còn lại, \(2 \le N \le 10000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
2
SE
5
EESSSESE

Case #1: ES
Case #2: SEEESSES

Nguồn

Google Code Jam 2019, Vòng loại, bài You Can Go Your Own Way.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.