Sau khi mạng lưới điện được sửa chữa, máy chiếu toàn ảnh cuối cùng đã khởi động thành công. Khi màn đêm buông xuống, máy chiếu toàn ảnh giữa không trung tỏa sáng rực rỡ. Mọi thứ đã sẵn sàng, T và S chính thức mở màn cho các hoạt động ban đêm, mời mọi người cùng tham gia vào trò chơi ánh sáng và bóng tối được chuẩn bị kỹ lưỡng, thử thách sự ăn ý của hai người mang tên "Giải mã ánh sáng".

Các chùm sáng ở trung tâm quảng trường đan xen vào nhau, dần dần hội tụ thành một cái cây ánh sáng hoàn chỉnh. Cây ánh sáng bao gồm một số nút là các cụm ánh sáng lơ lửng và các đường truyền ánh sáng nối giữa chúng, tạo thành cấu trúc cây thuần túy. Khi trò chơi bắt đầu, tất cả các đường truyền chưa được thắp sáng, người chơi không thể quan sát bất kỳ đường truyền nào. Karuha, người vận hành hệ thống, sẽ là người đầu tiên tiết lộ một con số bí ẩn cho người chơi đang đứng trước bảng điều khiển. Sau đó, các đường truyền ánh sáng sẽ lần lượt sáng lên, người chơi này phải quyết định hướng dòng chảy của mỗi đường truyền ngay tại thời điểm nó xuất hiện; trong khi đó, người đồng đội đứng ở phía bên kia sân khấu, chỉ dựa vào cấu trúc cây có hướng cuối cùng, phải suy luận chính xác con số bí ẩn này.

Là những người tham gia lễ hội, Neri và Noir quyết định hợp tác để hoàn thành thử thách này.

Trong thử thách này, Neri sẽ đứng trước bảng điều khiển. Karuha của hệ thống trước tiên sẽ đưa cho cô ấy hai số nguyên dương $n, s$ ($1 \le s \le 2^{n-1}$), lần lượt biểu thị số lượng cụm ánh sáng và con số bí ẩn của cây ánh sáng.

Sau đó, Karuha sẽ lần lượt thắp sáng $n - 1$ đường truyền ánh sáng, Neri phải quyết định hướng dòng chảy cho mỗi đường truyền ngay lập tức khi nó sáng lên.

Đối với Noir đứng ở phía bên kia sân khấu chính, cô ấy sẽ quan sát hình dạng cuối cùng của cây ánh sáng đầy ánh sáng. Cô ấy cần dựa vào hướng dòng chảy của các đường truyền này để suy luận ra con số bí ẩn $s$ mà Karuha đã truyền cho Neri.

Để giành chiến thắng trong thử thách ánh sáng này, Neri và Noir cần lập trước một chiến lược để đảm bảo vượt qua trò chơi thử thách sự ăn ý của hai người này một cách suôn sẻ.

Chương trình của bạn sẽ chạy độc lập hai lần, trong đó lần đầu tiên sẽ đóng vai Neri để quyết định hướng dòng chảy của mỗi đường truyền, lần thứ hai sẽ đóng vai Noir để suy luận ra con số bí ẩn dựa trên hình dạng cuối cùng của cây ánh sáng. Trình tương tác sẽ đóng vai Karuha, truyền thông tin đến chương trình của bạn.

Trong lần chạy đầu tiên, chương trình của bạn trước tiên sẽ nhận được số lượng cụm ánh sáng $n$ và con số bí ẩn $s$, sau đó lần lượt nhận được $n - 1$ đường truyền ánh sáng được thắp sáng. Chương trình của bạn cần ngay lập tức xuất ra hướng dòng chảy đã định cho đường truyền đó, từ đó truyền thông tin cho lần chạy thứ hai.

Trong lần chạy thứ hai, chương trình của bạn sẽ nhận được thông tin từ lần chạy đầu tiên từ trình tương tác, đó là hướng dòng chảy của các đường truyền trên cây ánh sáng, sau đó cần dựa vào những thông tin này để suy luận ra con số bí ẩn $s$ mà Karuha đã truyền cho Neri.

Mỗi bộ dữ liệu kiểm tra chứa nhiều nhóm dữ liệu thử nghiệm. Dòng đầu tiên của đầu vào chứa hai số nguyên dương $T, r$ ($1 \le T \le 10^4, r \in \{1, 2\}$), biểu thị số lượng nhóm dữ liệu và số thứ tự giai đoạn. Đối với mỗi nhóm dữ liệu:

• Nếu $r = 1$, thì:

  • Dòng đầu tiên nhập hai số nguyên dương $n, s$ ($3 \le n \le 30, 1 \le s \le 2^{n-1}$), lần lượt biểu thị số lượng cụm ánh sáng và con số bí ẩn của cây ánh sáng;
  • Tiếp theo sẽ lần lượt thắp sáng $n - 1$ đường truyền ánh sáng. Mỗi khi một đường truyền sáng lên, nhập hai số nguyên dương $u, v$ ($1 \le u < v \le n$), biểu thị hai cụm ánh sáng mà đường truyền kết nối, bạn cần ngay lập tức xuất ra một dòng gồm hai số nguyên dương $u, v$ hoặc $v, u$, biểu thị hướng dòng chảy là từ $u$ đến $v$ hoặc từ $v$ đến $u$.
  • Lưu ý: Đối với mỗi đường truyền ánh sáng, bạn phải xuất ra hướng dòng chảy của đường truyền đó và xóa bộ đệm đầu ra tiêu chuẩn, sau đó mới có thể tiếp tục nhập đường truyền sáng tiếp theo.

• Nếu $r = 2$, thì:

  • Dòng đầu tiên nhập một số nguyên dương $n$ ($3 \le n \le 30$), biểu thị số lượng cụm ánh sáng của cây ánh sáng;
  • Tiếp theo là $n - 1$ dòng, mỗi dòng nhập hai số nguyên dương $u, v$ ($1 \le u, v \le n$), biểu thị một đường truyền ánh sáng chảy từ cụm ánh sáng $u$ đến cụm ánh sáng $v$.
  • Bạn cần ngay lập tức xuất ra một dòng gồm một số nguyên dương, biểu thị con số bí ẩn $s$ đã suy luận được.
  • Lưu ý:
    • Thứ tự nhập dữ liệu thử nghiệm trong một bộ kiểm tra có thể khác so với lần chạy đầu tiên.
    • Đối với cùng một nhóm dữ liệu thử nghiệm, thứ tự nhập các đường truyền ánh sáng trong hai lần chạy có thể không nhất quán, nhưng số thứ tự của các cụm ánh sáng vẫn được giữ nguyên.
    • Đối với mỗi nhóm dữ liệu thử nghiệm, bạn phải xuất ra con số bí ẩn $s$ đã suy luận được và xóa bộ đệm đầu ra tiêu chuẩn, sau đó mới có thể tiếp tục nhập nhóm dữ liệu tiếp theo.

Ví dụ

Dữ liệu vào 1

2 1
7 21
1 6
3 5
2 4
3 4
1 2
6 7
9 59
1 2
1 4
3 4
3 5
3 8
5 6
6 7
8 9

Dữ liệu ra 1

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

1 2
1 4
3 4
3 5
8 3
5 6
6 7
9 8

Ghi chú

Các dòng trống ở trên chỉ để thuận tiện cho việc hiểu sự phân tách giữa hai nhóm dữ liệu thử nghiệm, chương trình thực tế không cần in thêm các dòng trống dư thừa. Sau khi định hướng các đường truyền ánh sáng của hai nhóm dữ liệu thử nghiệm, hình dạng của cây ánh sáng lần lượt như sau:

Hình 1: Nhóm dữ liệu thử nghiệm thứ nhất

Hình 2: Nhóm dữ liệu thử nghiệm thứ hai

Dựa trên kết quả xuất ra ở trên, lần chạy thứ hai, một đầu vào có thể xảy ra như sau:

Dữ liệu vào 2

2 2
9
9 8
1 2
5 6
6 7
1 4
3 5
8 3
3 4
7
1 2
4 2
6 1
3 5
3 4
7 6

Dữ liệu ra 2

59
21

Chi tiết kiểm thử

Tệp kịch bản treedir_testing_tool.py được cung cấp có thể hỗ trợ bạn thực hiện kiểm thử cục bộ để xác minh tính đúng đắn của chương trình và in ra quá trình tương tác chi tiết. Khi kiểm thử, hãy đặt tệp kịch bản này vào cùng thư mục với tệp thực thi đã biên dịch của bạn, sau đó chạy lệnh sau trong terminal:

python3 treedir_testing_tool.py [--quiet] <data_file> <program> <arguments>

Trong đó: -q, --quiet là tham số tùy chọn, sau khi sử dụng tham số này, kịch bản kiểm thử sẽ không còn in ra quá trình tương tác chi tiết. data_file là đường dẫn tệp đầu vào được cung cấp cho kịch bản kiểm thử. Tệp này cần đáp ứng định dạng sau: Dòng đầu tiên chứa hai số không âm $T, seed$, lần lượt đại diện cho số nhóm dữ liệu thử nghiệm và hạt giống ngẫu nhiên được sử dụng để xáo trộn thứ tự thử nghiệm và thứ tự các cạnh trong cây. Nếu chỉ định $seed = 0$, nghĩa là không thực hiện xáo trộn. Định dạng của mỗi nhóm dữ liệu hoàn toàn giống với định dạng đầu vào của "lần chạy đầu tiên" đã mô tả ở trên. program là đường dẫn đến tệp thực thi đã biên dịch của bạn. arguments là các tham số dòng lệnh bổ sung được truyền cho tệp thực thi đó.

Lưu ý: 1. Việc thực hiện thư viện tương tác của kịch bản kiểm thử và đánh giá thực tế không hoàn toàn giống nhau, kết quả kiểm thử cục bộ không có tính cuối cùng, chỉ dùng để tham khảo trong giai đoạn gỡ lỗi; 2. Kịch bản kiểm thử chỉ thực hiện kiểm tra định dạng cơ bản đối với dữ liệu trong data_file, không kiểm tra xem nó có đáp ứng hợp lệ các giới hạn của bài toán hay không (ví dụ: không kiểm tra xem $s$ có thỏa mãn giới hạn $1 \le s \le 2^{n-1}$ hay không, cũng không phán đoán xem các đường truyền ánh sáng có tạo thành một cái cây chính xác hay không); 3. Kịch bản kiểm thử không giám sát mức tiêu thụ thời gian và không gian của chương trình, không thể dùng để kiểm tra xem có đáp ứng giới hạn không gian và thời gian của bài toán hay không.