Có \(N\) hòn đảo, đánh số từ \(0\) đến \(N-1\), được nối bằng \(N-1\) cây cầu hai chiều. Có thể đi từ bất kỳ đảo nào đến bất kỳ đảo nào bằng cầu. Mỗi đảo nối trực tiếp với không quá \(18\) cây cầu, và có một chú hải ly sinh sống.

Khi đúng ba chú hải ly gặp nhau, chúng chọn hòn đảo làm tổng số cầu mà cả ba phải đi qua nhỏ nhất. Hòn đảo như vậy luôn tồn tại duy nhất và có thể là nơi ở của một trong ba chú.

Bạn muốn xác định tất cả các cây cầu nhưng không thể kiểm tra trực tiếp. Mỗi lần, bạn chọn ba đảo phân biệt \(u,v,w\), yêu cầu ba chú hải ly ở đó gặp nhau, rồi được biết đảo mà chúng chọn. Hãy tìm cấu trúc nối các đảo bằng ít yêu cầu nhất có thể.

Giao diện tương tác

Nộp tệp meetings.cpp, khai báo #include "meetings.h" và cài đặt:

void Solve(int N);

Hàm được gọi đúng một lần cho mỗi test; \(N\) là số đảo. Chương trình có thể gọi hai hàm do thư viện cung cấp:

int Query(int u, int v, int w);
void Bridge(int u, int v);

• Query(u, v, w) trả về đảo nơi ba chú hải ly gặp nhau. Các chỉ số phải thuộc \([0,N-1]\) và đôi một khác nhau, nếu không nhận Wrong Answer [1]. Không được gọi quá \(100\,000\) lần, nếu không nhận Wrong Answer [2].
• Bridge(u, v) báo rằng có cầu nối trực tiếp hai đảo. Phải có \(0\le u<v\le N-1\), nếu không nhận Wrong Answer [3]. Nếu không có cầu đó, nhận Wrong Answer [4]. Nếu báo cùng một cầu nhiều lần, nhận Wrong Answer [5]. Khi Solve kết thúc, phải đã gọi Bridge đúng \(N-1\) lần, nếu không nhận Wrong Answer [6].

Có thể khai báo biến toàn cục và hàm phụ. Không được đọc đầu vào chuẩn, ghi đầu ra chuẩn hoặc giao tiếp với các tệp khác bằng bất kỳ cách nào. Có thể ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Thư viện thử nghiệm

Gói thư viện mẫu chính thức chứa grader.cpp, meetings.h và mã nguồn mẫu. Đặt các tệp trong cùng thư mục và biên dịch bằng:

g++ -std=gnu++14 -O2 -o grader grader.cpp meetings.cpp

Trình chấm mẫu chạy trong một tiến trình, đọc đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn. Trình chấm thực tế khác trình chấm mẫu.

Dữ liệu vào

Đầu vào của trình chấm mẫu có dạng:

N
A_0 B_0
...
A_{N-2} B_{N-2}

Mỗi dòng \(A_i,B_i\) mô tả một cây cầu nối hai đảo đó.

Dữ liệu ra

Nếu chương trình trả lời đúng, trình chấm mẫu ghi số lần gọi Query, chẳng hạn Accepted: 100. Nếu có lỗi, nó ghi loại lỗi, chẳng hạn Wrong Answer [1]. Nếu có nhiều loại lỗi, chỉ một loại được báo.

Ràng buộc

• \(3\le N\le 2000\).
• \(0\le A_i<B_i\le N-1\) với \(0\le i\le N-2\).
• Có thể đi giữa mọi cặp đảo bằng cầu.
• Mỗi đảo nối trực tiếp với không quá \(18\) cây cầu.

Phân nhóm

1. (7 điểm) \(N\le 7\).
2. (10 điểm) \(N\le 50\).
3. (12 điểm) \(N\le 300\).
4. (71 điểm) Không có ràng buộc bổ sung.

Ở các nhóm \(1,2,3\), chỉ nhận toàn bộ điểm của nhóm khi trả lời đúng tất cả các test trong nhóm.

Ở nhóm \(4\), nếu trả lời đúng tất cả các test, gọi \(X\) là số lần gọi Query lớn nhất trong một test của nhóm. Điểm của nhóm là:

• \(49\) điểm nếu \(40\,000<X\le100\,000\).
• \(71\) điểm nếu \(X\le40\,000\).

Ví dụ giao tiếp

5
0 1
0 2
1 3
1 4

Một chuỗi lời gọi tương ứng:

Nguồn

JOI 2018/2019 Spring Training Camp, ngày 1. Đề gốc tiếng Anh, do Japanese Committee for the International Olympiad in Informatics công bố. Bản dịch tiếng Việt theo CC BY-SA 4.0.