Đây là một bài toán tương tác đa lượt. Hãy nhớ xóa bộ đệm đầu ra (flush) sau mỗi lần in. Để xóa bộ đệm đầu ra, bạn có thể sử dụng:
fflush(stdout)hoặccout.flush()trong C/C++;System.out.flush()trong Java và Kotlin;sys.stdout.flush()trong Python.
Trong trò chơi ghép cặp trực tuyến (online matching) cổ điển, các cạnh của đồ thị được tiết lộ từng cạnh một. Mỗi khi một cạnh được hiển thị, bạn phải ngay lập tức và không thể thay đổi quyết định xem có đưa nó vào tập ghép cặp của mình hay không. Mục tiêu của bạn là đảm bảo không có hai cạnh nào được chọn chia sẻ chung một đỉnh, đồng thời tối đa hóa tổng số cạnh được chọn.
Bạn là một nhà khoa học máy tính đầy tham vọng, khao khát danh tiếng. Như bạn đã biết, việc tìm ghép cặp cực đại trong môi trường trực tuyến là điều không thể thực hiện được với xác suất cao — ngay cả đối với những lớp đồ thị đơn giản nhất như đồ thị hai phía. Tuy nhiên, nơi người khác nhìn thấy một rào cản cơ bản, bạn lại nhìn thấy cơ hội để đạt được vinh quang. Hôm nay, bạn tuyên bố đã giải được bài toán mở lâu đời cho cây và sẵn sàng công bố thuật toán đột phá của mình với thế giới.
Chỉ có một vấn đề: hôm qua, bạn đã phát hiện ra một lỗi trong chứng minh của mình và bạn vẫn chưa biết cách sửa nó. Không muốn từ bỏ ánh đèn sân khấu, bạn quyết định biến buổi trình diễn của mình thành một màn ảo thuật — trợ lý của bạn, ẩn nấp sau hậu trường, sẽ truyền một gợi ý nhỏ về toàn bộ cái cây với $n$ đỉnh trước khi trò chơi bắt đầu.
Kế hoạch ban đầu của bạn rất đơn giản: để trợ lý gửi câu trả lời cho mỗi truy vấn cạnh trực tiếp. Để làm điều này, bạn đã cài đặt một chiếc tai nghe bí mật có khả năng nhận một chuỗi nhị phân duy nhất có độ dài $(n - 1)$. Nhưng khán giả lại hoài nghi về "bước đột phá" của bạn. Để ngăn chặn bất kỳ sự gian lận nào đã được sắp đặt trước, họ yêu cầu các cạnh phải được trình bày theo một thứ tự ngẫu nhiên đồng nhất — thứ tự mà cả bạn và trợ lý của bạn đều không thể dự đoán hoặc kiểm soát.
Sân khấu đã sẵn sàng. Ánh đèn đang chiếu vào bạn. Bây giờ hãy chứng minh tuyên bố của bạn — mà không cần thay đổi kênh.
Giao tiếp
Giải pháp của bạn được thực thi hai lần trong mỗi bài kiểm tra. Trong vòng prepare, giải pháp của bạn sẽ đóng vai trò là trợ lý. Trong vòng play, giải pháp của bạn sẽ đóng vai trò là bạn, nhà ảo thuật. Trong cả hai vòng, giải pháp của bạn sẽ được đánh giá như một thủ tục tương tác.
Vòng Prepare
Dòng đầu tiên của dữ liệu vào chứa từ prepare. Dòng thứ hai chứa một số nguyên $n$ ($2 \le n \le 500$) — số lượng đỉnh. $(n - 1)$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$ ($1 \le u, v \le n, u < v$), biểu thị một cạnh vô hướng giữa $u$ và $v$ trong cây.
Bạn phải xuất ra một dòng chứa một chuỗi nhị phân $s$ có độ dài chính xác là $(n - 1)$ bao gồm các ký tự 0 và 1. Đây là chuỗi được truyền đến vòng play thứ hai. Nếu đầu ra của bạn không tuân thủ định dạng mong muốn, bạn sẽ nhận được kết quả Wrong Answer.
Vòng Play
Giải pháp của bạn sẽ được khởi động lại cho vòng play.
Dòng đầu tiên chứa từ play. Dòng thứ hai chứa số nguyên $n$. Dòng thứ ba chứa chuỗi nhị phân $s$ chính xác như những gì bạn đã in trong vòng prepare.
Sau đó, trò chơi bắt đầu với $(n - 1)$ lượt. Trong mỗi lượt, một dòng chứa hai số nguyên $u$ và $v$ ($1 \le u, v \le n, u < v$) sẽ được cung cấp. Để phản hồi, bạn nên xuất ra một dòng chứa take hoặc ignore. Tất cả các cạnh trong vòng đầu tiên sẽ được cung cấp chính xác một lần, và thứ tự của các cạnh được chọn ngẫu nhiên đồng nhất từ $(n - 1)!$ hoán vị có thể.
Khi có đầu ra ở định dạng không hợp lệ, trò chơi sẽ kết thúc ngay lập tức mà không có thêm thông tin nào từ bộ tương tác.
Đánh giá độ chính xác
Gọi $M$ là tập hợp các cạnh mà giải pháp của bạn chọn. Kết quả được coi là chấp nhận được nếu không có đỉnh nào liên thuộc với nhiều hơn một cạnh được chọn và $|M| = |M^*|$, trong đó $M^*$ là ghép cặp cực đại của đồ thị.
Có chính xác 50 bài kiểm tra, không bao gồm các bài kiểm tra mẫu. Để vượt qua bài toán, giải pháp của bạn phải đúng trên tất cả các bài kiểm tra, bao gồm cả các bài kiểm tra mẫu.
Tất cả các lần xáo trộn được đảm bảo cố định trước khi nhận đầu ra của giải pháp. Tính ngẫu nhiên được cố định cho mỗi bài kiểm tra, được thực hiện bằng cách cố định hạt giống của bộ tạo số giả ngẫu nhiên.
Một công cụ kiểm tra được cung cấp để giúp bạn phát triển và kiểm tra giải pháp của mình.
Ví dụ
Dữ liệu vào 1 (Vòng 1)
prepare 3 1 2 1 3
Dữ liệu ra 1 (Vòng 1)
00
Dữ liệu vào 2 (Vòng 2)
play 3 00 1 3
Dữ liệu ra 2 (Vòng 2)
take
Dữ liệu vào 3 (Vòng 2)
1 2
Dữ liệu ra 3 (Vòng 2)
ignore
Ghi chú
Giải thích cho Ví dụ 1: Vì $|M^*| = 1$, việc chọn bất kỳ cạnh nào cũng đều chấp nhận được, và gợi ý có thể là tùy ý.
Figure 1. Magically Marked Matching Master