Ueli và Vreni đang chơi một trò chơi. Bàn chơi là một cây có \(N\) đỉnh, ban đầu tất cả đều màu xanh dương. Hai người lần lượt đi, Ueli đi trước. Trong mỗi lượt, người chơi phải chọn một đỉnh xanh, cùng với một tập con bất kỳ, có thể rỗng hoặc gồm tất cả, các hàng xóm xanh của đỉnh đó, rồi tô đỏ toàn bộ những đỉnh đã chọn. Nếu khi bắt đầu lượt của một người mà mọi đỉnh đều đã đỏ, người đó thua và người còn lại thắng.

Trong ván ví dụ dưới đây, lượt đầu Ueli tô đỏ đỉnh \(3\). Sau đó Vreni chọn đỉnh \(2\) và tô đỏ cả nó lẫn hàng xóm là đỉnh \(1\). Vì lúc này mọi đỉnh đều đỏ, Ueli thua và Vreni thắng.

Ueli và Vreni nhận thấy Ueli dễ thắng hơn nhiều vì được đi trước. Do đó họ dùng quy trình sau: trước hết Ueli chọn một số nguyên \(N\); tiếp theo Vreni chọn một cây bất kỳ có \(N\) đỉnh; rồi họ bắt đầu chơi như mô tả, Ueli đi lượt đầu.

Vreni hy vọng quyền chọn cây sẽ giúp cô vượt qua bất lợi đi sau. Hãy chứng minh điều đó bằng cách giúp Vreni thắng trong thiết lập này.

Dữ liệu vào

Đây là bài tương tác. Hãy bảo đảm bạn đã đọc phần Interactive Problems trong FAQ của Google Code Jam.

Ban đầu, chương trình đọc một dòng chứa số nguyên \(T\), số bộ test. Sau đó phải xử lý \(T\) bộ test.

Dữ liệu ra

Trong mỗi bộ test, chương trình phải in một cây, rồi gửi các nước đi theo giao thức tương tác bên dưới. Sau mỗi lần in dữ liệu, phải đẩy bộ đệm đầu ra.

Giao thức tương tác

Với mỗi bộ test, trước hết chương trình đọc một dòng chứa \(N\), số đỉnh Ueli chọn. Sau đó chương trình phải in \(N-1\) dòng mô tả các cạnh của cây Vreni chọn. Các đỉnh đánh số từ \(1\) tới \(N\). Mỗi dòng biểu diễn một cạnh riêng biệt bằng hai số nguyên thuộc \([1,N]\), là hai đầu cạnh. Toàn bộ các cạnh phải tạo thành một cây. Hai đầu cạnh có thể in theo bất kỳ thứ tự nào, và \(N-1\) dòng cũng có thể theo bất kỳ thứ tự nào.

Tiếp theo, chương trình đọc một dòng chứa \(M\), số ván phải chơi trên cây này. Các ván độc lập: mọi đỉnh lại xanh ở đầu mỗi ván.

Trong mỗi ván, cần xử lý một số lượt trao đổi cho tới khi ván kết thúc. Mỗi lượt trao đổi gồm một nước của mỗi người.

Đầu mỗi lượt trao đổi, chương trình đọc hai dòng mô tả nước của Ueli. Dòng đầu chứa số nguyên \(K\), số đỉnh xanh sẽ được tô đỏ. Dòng thứ hai chứa \(K\) số nguyên đôi một khác nhau \(A_1,A_2,\ldots,A_K\), là các đỉnh xanh được tô đỏ. Luôn có \(K\ge1\), mỗi \(A_i\) thuộc \([1,N]\), và mọi đỉnh \(A_2,A_3,\ldots,A_K\) đều là hàng xóm của \(A_1\).

Sau đó, chương trình phải in nước của Vreni theo cùng định dạng: dòng đầu là số đỉnh xanh sẽ tô đỏ, dòng thứ hai là các số đỉnh, theo thứ tự sao cho mọi đỉnh trừ đỉnh đầu đều là hàng xóm của đỉnh đầu.

Nếu sau lượt của Vreni mọi đỉnh đều đỏ, Vreni đã thắng và ván kết thúc. Ván kế tiếp bắt đầu ngay nếu còn; nếu đó là ván cuối của test, test kế tiếp bắt đầu ngay nếu còn. Nếu đây là test cuối, bộ chấm không gửi thêm gì và chương trình cũng không được gửi thêm gì.

Ngược lại, nếu sau nước của Ueli mọi đỉnh đều đỏ, Vreni đã thua nên chương trình không vượt qua test. Thay vì bắt đầu lượt trao đổi mới bằng một nước cuối tô đỏ mọi đỉnh còn lại, bộ chấm in một số \(-1\), không gửi thêm gì và không xử lý thêm ván hay test nào.

Nếu tại bất kỳ thời điểm nào bộ chấm nhận một dòng sai định dạng hoặc không hợp lệ — chẳng hạn sai số lượng số nguyên, số ngoài miền, tập cạnh không tạo thành cây, cố tô đỉnh đã đỏ, hoặc cố tô một đỉnh không phải hàng xóm của đỉnh đầu trong lượt — bộ chấm cũng in \(-1\) rồi không gửi thêm gì. Nếu chương trình tiếp tục chờ sau khi nhận \(-1\), nó sẽ hết thời gian. Bạn có trách nhiệm cho chương trình thoát kịp để nhận Wrong Answer thay vì Time Limit Exceeded. Như thường lệ, vượt giới hạn bộ nhớ hoặc lỗi chạy sẽ nhận phán quyết tương ứng.

Bộ chấm có tính xác định: hai lần nộp in cùng các số sẽ nhận cùng dữ liệu vào. Dĩ nhiên, bộ chấm vẫn có thể thực hiện những nước khác nhau ở các ván khác nhau trên cùng một cây.

Ràng buộc

• \(1\le M\le50\).

Phân nhóm

• Test Set 1 (phán quyết hiển thị): \(T=1\), \(N=30\).
• Test Set 2 (phán quyết ẩn): \(1\le T\le10\), \(31\le N\le40\), và không hai test nào dùng cùng một \(N\).

Công cụ kiểm thử

Bạn có thể dùng công cụ kiểm thử để chạy cục bộ hoặc trên nền tảng. Khi chạy cục bộ, cần chạy công cụ song song với chương trình; có thể dùng interactive runner. Hãy đọc hướng dẫn trong phần chú thích của tệp đó và phần Interactive Problems trong FAQ.

Hướng dẫn cho công cụ nằm trong các chú thích bên trong nó. Bạn được khuyến khích thêm test riêng. Dù công cụ nhằm mô phỏng hệ thống chấm, nó không phải hệ thống chấm thật và có thể hành xử khác. Nếu mã vượt qua công cụ nhưng trượt bộ chấm thật, hãy kiểm tra phần Coding trong FAQ để bảo đảm dùng cùng trình biên dịch với hệ thống chính thức.

Công cụ kiểm thử chỉ chọn ngẫu nhiên nước của Ueli, trừ khi Ueli có thể thắng trong một lượt. Vì thế, thắng công cụ có thể dễ hơn thắng bộ chấm thật, vốn sẽ cố gắng thắng hơn.

Ví dụ

2

3

1 2
1 3

1

1
3

2
1 2

4

1 2
2 3
2 4

2

3
2 1 3

1
4

2
2 3

1
1

-1

Nguồn

Google Code Jam 2022, Vòng 3, bài Win As Second.

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