Gooli là một công ty khổng lồ sở hữu \(B\) tòa nhà trong một vùng đồi núi, được đánh số từ \(1\) đến \(B\). Sáu năm trước, Gooli đã xây các đường trượt để nhân viên đi từ tòa nhà này sang tòa nhà khác. Mỗi đường trượt cho phép đi từ tòa nhà đầu đến tòa nhà cuối của nó, nhưng không cho phép đi theo chiều ngược lại. Tổng giám đốc Gooli rất tự hào về các đường trượt và muốn tổ chức một cuộc diễu hành qua chúng. Bà giao cho Melek, Trưởng bộ phận Giao thông kiêm người đam mê giải bài toán của Gooli, thiết kế lộ trình diễu hành.

Bà đặt ra các yêu cầu sau cho lộ trình:

• Lộ trình phải bắt đầu và kết thúc ở tòa nhà \(1\), nơi đặt văn phòng của bà.
• Lộ trình phải ghé thăm mỗi tòa nhà cùng một số lần. Việc có mặt ở tòa nhà \(1\) lúc bắt đầu lộ trình không được tính là một lần ghé thăm.
• Lộ trình phải sử dụng mỗi đường trượt ít nhất một lần.
• Lộ trình phải có nhiều nhất \(10^6\) bước.

Cho sơ đồ các tòa nhà và đường trượt, hãy giúp Melek tìm một lộ trình thỏa tất cả yêu cầu của tổng giám đốc nếu lộ trình đó tồn tại.

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Sau đó là \(T\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên \(B\) và \(S\), lần lượt là số tòa nhà và số đường trượt.

Tiếp theo là \(S\) dòng. Dòng thứ \(i\) chứa hai số nguyên \(U_i\) và \(V_i\), cho biết đường trượt thứ \(i\) đi từ tòa nhà \(U_i\) đến tòa nhà \(V_i\).

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ \(1\)). Nếu không có lộ trình thỏa mọi yêu cầu, \(y\) phải là IMPOSSIBLE. Nếu có, \(y\) phải là một số nguyên trong đoạn từ \(S+1\) đến \(10^6+1\), kể cả hai đầu, biểu diễn số tòa nhà trong một lộ trình mà bạn muốn đưa ra.

Trong trường hợp thứ hai, in thêm một dòng chứa \(y\) số nguyên \(z_1\ z_2\ \dots\ z_y\), trong đó \(z_j\) là tòa nhà thứ \(j\) trên lộ trình đề xuất. Lưu ý rằng \(z_1=z_y=1\), và mỗi tòa nhà phải xuất hiện cùng một số lần trong các \(z_j\), ngoại trừ tòa nhà \(1\) xuất hiện nhiều hơn đúng một lần.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le U_i \le B\) với mọi \(i\).
• \(1 \le V_i \le B\) với mọi \(i\).
• \(U_i \ne V_i\) với mọi \(i\).
• \((U_i,V_i)\ne(U_j,V_j)\) với mọi \(i\ne j\).

Phân nhóm

• Test Set 1 (phán quyết hiển thị): \(2\le B\le10\) và \(2\le S\le10\).
• Test Set 2 (phán quyết ẩn): \(2\le B\le200\) và \(2\le S\le5000\).

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

5
2 2
2 1
1 2
3 4
2 3
1 2
3 2
1 3
3 6
1 2
1 3
2 1
2 3
3 1
3 2
3 4
1 2
2 1
1 3
3 1
4 6
1 2
1 4
2 3
3 2
3 4
4 1

Case #1: 7
1 2 1 2 1 2 1
Case #2: IMPOSSIBLE
Case #3: 7
1 2 3 1 3 2 1
Case #4: IMPOSSIBLE
Case #5: 9
1 4 1 2 3 2 3 4 1

Nguồn

Google Code Jam 2022, Chung kết thế giới, bài Slide Parade.

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