Đội ngũ Google Coding Competitions đang xây dựng một công viên chủ đề mới. Như mọi công viên tốt khác, họ muốn có các diễn viên hóa trang thành linh vật để tương tác với khách. Vì cần mở cửa gấp, họ quyết định dùng các chữ cái trong CODE JAM, KICK START và HASH CODE làm linh vật, tổng cộng \(13\) linh vật khác nhau: ACDEHIJKMORST.

Điểm vui chơi duy nhất của công viên là một mê cung gồm \(N\) phòng, đánh số từ \(1\) đến \(N\). Mỗi phòng có một lối ra bên trái và một lối ra bên phải; mỗi lối dẫn khách tới một phòng khác. Không thể đi ngược chiều một lối ra. Chẳng hạn, nếu phòng \(2\) có lối sang phòng \(3\), khách không thể từ phòng \(3\) quay lại phòng \(2\), trừ khi chính phòng \(3\) cũng có một lối dẫn tới phòng \(2\).

Ta muốn đặt đúng một trong \(13\) linh vật vào mỗi phòng. Mỗi chữ cái có thể xuất hiện ở không phòng nào, một phòng hoặc nhiều phòng. Để tăng tính đa dạng, mọi ba phòng, không nhất thiết phân biệt, mà một du khách có thể ghé liên tiếp phải có ba linh vật khác nhau.

Hãy chọn linh vật cho mỗi phòng sao cho đạt mục tiêu, hoặc cho biết điều đó không thể thực hiện.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm ba dòng. Dòng đầu chứa số nguyên \(N\), số phòng trong mê cung. Dòng thứ hai chứa \(N\) số nguyên \(L_1,L_2,\ldots,L_N\), nghĩa là lối trái từ phòng \(i\) dẫn tới phòng \(L_i\). Dòng cuối chứa \(N\) số nguyên \(R_1,R_2,\ldots,R_N\), nghĩa là lối phải từ phòng \(i\) dẫn tới phòng \(R_i\).

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó \(x\) là số thứ tự bộ test, bắt đầu từ \(1\). Nếu không thể gán linh vật tuân thủ các quy tắc, \(y\) là IMPOSSIBLE. Nếu có thể, \(y\) là chuỗi dài \(N\); ký tự thứ \(i\) phải là một chữ hoa trong ACDEHIJKMORST, chỉ linh vật đặt ở phòng \(i\).

Ràng buộc

• \(1\le T\le100\).
• \(L_i\ne i\) và \(R_i\ne i\) với mọi \(i\).
• \(1\le L_i<R_i\le N\) với mọi \(i\).

Phân nhóm

• Test Set 1 (phán quyết hiển thị): \(3\le N\le100\).
• Test Set 2 (phán quyết ẩn): \(3\le N\le10^5\).

Đ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ụ

4
3
2 1 1
3 3 2
6
3 1 4 1 2 3
5 3 5 2 4 5
20
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 1 1
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 20 2
19
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 1
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 19 3

Case #1: IMPOSSIBLE
Case #2: TSHIRT
Case #3: HCJKSHCJKSHCJKSHCJKS
Case #4: CODEJAMROCKSTHEMOST

Nguồn

Google Code Jam 2022, Vòng 3, bài Mascot Maze.

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