Ann và người bạn Kathrin gần đây đã khám phá ra một trò chơi bàn cờ mới và trò chơi này đã trở thành trò yêu thích của họ: Laser Strike. Trong trò chơi này, hai người chơi phối hợp để loại bỏ ~N~ quân cờ khỏi bàn. Trò chơi diễn ra qua hai pha. Điểm khó là Kathrin sẽ không có đầy đủ thông tin về trò chơi. Để giành chiến thắng, Ann và Kathrin phải phối hợp với nhau, đồng thời trao đổi càng ít thông tin càng tốt.

Trên bàn có ~N~ quân cờ phân biệt, được đánh số từ ~0~ đến ~N-1~. Cả hai người chơi đều có thể nhìn thấy các quân cờ này. Ngoài ra, có ~N-1~ liên kết giữa các cặp quân cờ, sao cho có thể đi từ một quân cờ bất kỳ đến mọi quân cờ khác bằng cách đi theo các liên kết đó. Nói cách khác, các liên kết này tạo thành một cây. Chỉ Ann nhìn thấy các liên kết này; Kathrin không biết chúng.

Trong pha đầu tiên của trò chơi, Ann quyết định thứ tự ~\ell_0, \ell_1, \dots, \ell_{N-2}~ để loại bỏ các quân cờ, cho đến khi chỉ còn lại một quân. Thứ tự này được giữ bí mật với Kathrin. Nếu Kathrin có thể thực hiện lại đúng thứ tự đó, họ sẽ thắng trò chơi. Việc loại bỏ các quân cờ phải tuân theo quy tắc sau: mỗi khi một quân cờ bị loại bỏ, nó phải liên kết với đúng một quân cờ còn lại. Nói cách khác, quân cờ bị loại bỏ phải là một lá của cây tạo bởi chính nó và các quân cờ còn lại. (Sau khi ~N-1~ quân cờ đã bị loại bỏ, quân cuối cùng được tự động loại bỏ và hai người chơi giành chiến thắng.) Ann phải chọn một thứ tự tuân theo quy tắc trên.

Ann cũng sẽ viết một thông điệp gửi cho Kathrin dưới dạng một xâu nhị phân. Ann có thể chọn độ dài của thông điệp này — nhưng thông điệp càng ngắn thì họ càng nhận được nhiều điểm.

Sau đó, pha thứ hai của trò chơi bắt đầu. Mục tiêu của trò chơi là để Kathrin loại bỏ ~N-1~ quân cờ khỏi bàn theo thứ tự ~\ell_0, \ell_1, \dots, \ell_{N-2}~. Kathrin sẽ thực hiện ~N-1~ lượt đi. Trước lượt đi thứ ~i~, Ann cho Kathrin biết một cặp số nguyên ~a~, ~b~ có các tính chất sau:

• ~a < b~;

• vẫn còn một cặp quân cờ liên kết trực tiếp với nhau, có số hiệu là ~a~ và ~b~; và

• một trong hai quân ~a~ hoặc ~b~ là quân ~\ell_i~ cần được loại bỏ trong lượt đi này.

Lưu ý rằng đối với Ann, liên kết ~(a,b)~ được xác định duy nhất bởi lá ~\ell_i~ trong cây hiện tại.

Sau đó, Kathrin loại bỏ quân ~a~ hoặc quân ~b~ khỏi bàn. Nếu đó là quân cờ đúng — tức là ~\ell_i~ — họ tiếp tục chơi. Nếu không, họ thua trò chơi.

Nhiệm vụ của bạn là cài đặt chiến lược của cả Ann và Kathrin để họ thắng trò chơi.

Chương trình của bạn sẽ được chấm điểm dựa trên độ dài thông điệp mà Ann viết trong pha đầu tiên của trò chơi.

Đây là một bài toán chạy nhiều lần, nghĩa là chương trình của bạn sẽ được thực thi hai lần. Trong lần chạy đầu tiên, chương trình cần thực hiện chiến lược của Ann cho pha đầu tiên của trò chơi. Sau đó, chương trình cần thực hiện chiến lược của Kathrin cho pha thứ hai của trò chơi.

Input

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên ~P~ và ~N~, trong đó ~P~ bằng ~1~ hoặc ~2~ (pha thứ nhất hoặc pha thứ hai), còn ~N~ là số quân cờ.

Phần dữ liệu vào tiếp theo phụ thuộc vào pha:

Pha 1: Ann

Sau dòng đầu tiên (được mô tả ở trên), ~N-1~ dòng tiếp theo của dữ liệu vào mô tả cây. Mỗi dòng chứa hai số ~a~ và ~b~ (~0 \le a < b \le N-1~), biểu thị một liên kết giữa hai quân cờ ~a~ và ~b~.

Pha 2: Kathrin

Sau dòng đầu tiên (được mô tả ở trên), dòng tiếp theo của dữ liệu vào chứa xâu nhị phân (thông điệp của Ann) từ pha ~1~.

Sau đó sẽ có ~N-1~ lượt tương tác, mỗi lượt ứng với một lượt đi của Kathrin.

Trong lượt đi thứ ~i~, chương trình của bạn trước tiên cần đọc hai số ~a~ và ~b~ (~0 \le a < b \le N-1~). Một trong hai quân cờ này là lá ~\ell_i~ trong thứ tự của Ann, còn quân kia là quân cờ còn lại duy nhất liên kết với ~\ell_i~.

Output

Pha 1: Ann

Chương trình của bạn cần bắt đầu bằng việc in ra một xâu nhị phân có nhiều nhất ~1000~ ký tự, mỗi ký tự là '0' hoặc '1', biểu diễn thông điệp do Ann viết. Lưu ý rằng để tạo một xâu có độ dài ~0~, chương trình cần in ra một dòng trống.

Sau đó, chương trình cần in ra ~N-1~ số nguyên ~\ell_0, \ell_1, \dots, \ell_{N-2}~, mỗi số trên một dòng riêng, biểu thị thứ tự mà Ann muốn loại bỏ các lá của cây. Thứ tự này phải bảo đảm rằng khi các quân cờ được lần lượt loại bỏ khỏi cây theo thứ tự đó, quân cờ bị loại bỏ luôn là một lá, tức là cây phải luôn liên thông.

Pha 2: Kathrin

Tiếp đó, chương trình của bạn cần in ra ~\ell_i~, biểu thị rằng Kathrin loại bỏ lá này. Nếu chương trình không in ra đúng lá ~\ell_i~, hai cô gái thua trò chơi và bài nộp của bạn sẽ nhận kết quả Wrong Answer cho test này.

Chi tiết

Nếu tổng thời gian chạy của hai lần thực thi riêng biệt của chương trình vượt quá giới hạn thời gian, bài nộp của bạn sẽ nhận kết quả Time Limit Exceeded.

Hãy nhớ đẩy dữ liệu ra đầu ra chuẩn sau khi in mỗi dòng; nếu không, chương trình của bạn có thể nhận kết quả Time Limit Exceeded. Trong Python, việc này diễn ra tự động miễn là bạn sử dụng input() để đọc các dòng. Trong C++, cout << endl; vừa in ký tự xuống dòng vừa đẩy dữ liệu ra; nếu dùng printf, hãy sử dụng fflush(stdout);.

Lưu ý rằng việc đọc đúng một xâu rỗng có thể khá khó. Các chương trình mẫu được cung cấp xử lý đúng trường hợp này.

Scoring

• ~N=1000~.

• ~0 \le a < b \le N-1~ với mọi liên kết.

Lời giải của bạn sẽ được kiểm tra trên một số nhóm test, mỗi nhóm có một số điểm nhất định. Mỗi nhóm test chứa một tập hợp các test. Để nhận được điểm của một nhóm test, bạn cần giải đúng tất cả các test trong nhóm đó.

Subtask	Điểm	Ràng buộc
1	~8~	Cây có dạng hình sao. Nghĩa là tất cả các đỉnh, trừ một đỉnh, đều là lá.
2	~9~	Cây là một đường đi. Nghĩa là tất cả các đỉnh, trừ hai đỉnh lá, đều có đúng hai đỉnh kề.
3	~21~	Cây có dạng hình sao với các nhánh là đường đi. Nghĩa là tất cả các đỉnh đều có một hoặc hai đỉnh kề, ngoại trừ một đỉnh có nhiều hơn hai đỉnh kề.
4	~36~	Khoảng cách giữa hai đỉnh bất kỳ không vượt quá ~10~.
5	~26~	Không có giới hạn gì thêm

Với mỗi nhóm test mà chương trình giải đúng, bạn sẽ nhận được số điểm tính theo công thức sau:

~\text{score}=S_g \cdot \left(1-0.3 \cdot \log_{10}\max(K,1)\right)~,

trong đó ~S_g~ là số điểm tối đa của nhóm test, còn ~K~ là độ dài lớn nhất của thông điệp Ann cần gửi trong một test bất kỳ thuộc nhóm đó. Điểm của bạn cho mỗi nhóm test sẽ được làm tròn đến số nguyên gần nhất.

Bảng dưới đây cho biết số điểm mà chương trình của bạn sẽ nhận được với một vài giá trị của ~K~, nếu chương trình giải đúng tất cả các nhóm test với giá trị ~K~ đó. Cụ thể, để đạt ~100~ điểm, lời giải của bạn phải giải đúng mọi test với ~K \le 1~.

~K~	~1~	~5~	~10~	~50~	~100~	~500~	~1000~
Điểm	~100~	~79~	~70~	~49~	~39~	~20~	~11~

Sample Input 1

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

Sample Output 1

0110
5
3
2
6
4
0

Sample Input 2

2 7
0110
1 5
2 3
1 2
0 6
0 4
0 1

Sample Output 2

5
3
2
6
4
0

Notes

Công cụ kiểm thử

Để giúp bạn kiểm thử lời giải, chúng tôi cung cấp một công cụ đơn giản mà bạn có thể tải xuống. Xem mục 'attachments' ở cuối trang đề bài trên Kattis. Việc sử dụng công cụ này là không bắt buộc. Lưu ý rằng chương trình chấm chính thức trên Kattis khác với công cụ kiểm thử.

Để sử dụng công cụ, hãy tạo một tệp dữ liệu vào, chẳng hạn 'sample1.in', bắt đầu bằng một số ~N~, theo sau là ~N-1~ dòng mô tả cây theo cùng định dạng như trong pha ~1~. Chẳng hạn, với ví dụ bên dưới:

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

Với chương trình Python, giả sử có tên solution.py (thường được chạy bằng pypy3 solution.py):

python3 testing_tool.py pypy3 solution.py < sample1.in

Với chương trình C++, trước tiên hãy biên dịch (chẳng hạn bằng g++ -g -O2 -std=gnu++23 -static solution.cpp -o solution.out), rồi chạy:

python3 testing_tool.py ./solution.out < sample1.in

Giải thích ví dụ

Lưu ý rằng để đơn giản, ví dụ trong phần này có ~N=7~ và do đó không phải là một test hợp lệ. Chương trình của bạn không được yêu cầu phải giải được trường hợp này. Tất cả các test trên hệ thống chấm đều có ~N=1000~.

Trong ví dụ, Ann được cho cây trong Sample Input ~1~. Trong pha đầu tiên, Ann đọc cây, chọn xâu nhị phân "0110" để gửi cho Kathrin, đồng thời chọn thứ tự ~[\ell_0,\ell_1,\dots,\ell_{N-2}]=[5,3,2,6,4,0]~ để loại bỏ các quân cờ khỏi cây. Trong pha thứ hai, Kathrin nhận được xâu "0110" đã được gửi trong pha đầu tiên. Sau đó, Kathrin nhận được cặp ~(1,5)~ và quyết định loại bỏ đỉnh ~5~, đúng là một lá. Ở lượt đi tiếp theo, Kathrin nhận được cặp ~(2,3)~ và loại bỏ lá ~3~, và cứ như vậy.

Sample Input ~1~ và Sample Output ~1~ mô tả lần chạy đầu tiên (Ann). Sample Input ~2~ và Sample Output ~2~ mô tả lần chạy thứ hai (Kathrin). Trong lần chạy thứ hai, mỗi cặp số chỉ được gửi sau khi chương trình đã trả lời cặp trước đó; chương trình phải in câu trả lời trước khi đọc cặp tiếp theo.

Ghi công và giấy phép

Bài toán này có nguồn gốc từ EGOI 2025 (Olympic Tin học nữ châu Âu), Ngày 2, được tổ chức tại Bonn, Đức.

• Đề bài gốc: Laser Strike

• Tác giả: Luca Versari.

• Chủ sở hữu bản quyền: Olympic Tin học nữ châu Âu 2025.

• Tài liệu chính thức: Đề bài và lời giải · Dữ liệu kiểm thử, trình chấm và các bản dịch

• Giấy phép: Creative Commons Ghi công – Chia sẻ tương tự (CC BY-SA), theo siêu dữ liệu chính thức của bài toán. Siêu dữ liệu không chỉ rõ phiên bản giấy phép.

• Các thay đổi: Dịch sang tiếng Việt và định dạng lại cho ClueOJ.

Bản dịch này được phân phối theo cùng các điều khoản CC BY-SA áp dụng cho bài toán gốc.

ClueOJ không có quan hệ liên kết với EGOI hoặc ban tổ chức EGOI 2025, cũng không được các bên này chứng thực.