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

Đôi khi, một số con hải ly tập trung tại một hòn đảo để họp. Khi có đúng ba con hải ly họp, chúng tập trung tại hòn đảo sau:

Hòn đảo làm cho tổng số cây cầu mà ba con hải ly đi qua để tập trung là nhỏ nhất (hòn đảo như vậy tồn tại duy nhất).

Lưu ý rằng hòn đảo này có thể chính là nơi sinh sống của một trong ba con hải ly.

Bạn muốn biết $N$ hòn đảo được nối với nhau bằng cầu như thế nào. Bạn không thể trực tiếp đến kiểm tra các hòn đảo, vì vậy bạn sẽ đưa ra một số chỉ thị cho các con hải ly. Một chỉ thị gồm các bước sau:

• Bạn chỉ định ba hòn đảo $u$, $v$ và $w$ ($0\le u\le N-1$, $0\le v\le N-1$, $0\le w\le N-1$, $u\ne v$, $u\ne w$, $v\ne w$), và yêu cầu các con hải ly sống trên các hòn đảo $u$, $v$ và $w$ họp với nhau.
• Sau đó, bạn có thể biết hòn đảo nơi ba con hải ly tập trung.

Bạn muốn xác định cách các hòn đảo được nối với nhau bằng ít chỉ thị.

Hãy viết một chương trình nhận số lượng hòn đảo, giao tiếp với các con hải ly và xác định cách các hòn đảo được nối với nhau.

Chi tiết cài đặt

Bạn cần nộp một tệp.

Tên tệp là meetings.cpp. Tệp này phải cài đặt hàm sau. Chương trình phải bao gồm meetings.h.

• void Solve(int N)

  Hàm này được gọi đúng một lần cho mỗi bộ kiểm thử.

  • Tham số N biểu diễn $N$, số lượng hòn đảo.

  Chương trình của bạn có thể gọi các hàm sau.

  • int Query(int u, int v, int w)

    Với chỉ số của ba hòn đảo mà bạn chỉ định, hàm này trả về chỉ số hòn đảo nơi các con hải ly sống trên ba hòn đảo đó tập trung để họp.

    • Bạn chỉ định các chỉ số $u$, $v$ và $w$ của ba hòn đảo lần lượt qua các tham số u, v và w. Chúng phải thỏa mãn $0\le u\le N-1$, $0\le v\le N-1$, $0\le w\le N-1$, $u\ne v$, $u\ne w$ và $v\ne w$. Nếu không, chương trình bị coi là Wrong Answer [1].
    • Không được gọi hàm Query quá $100\,000$ lần. Nếu không, chương trình bị coi là Wrong Answer [2].

  • void Bridge(int u, int v)

    Bạn dùng hàm này để trả lời cách các hòn đảo được nối với nhau bằng cầu.

    • Các tham số u và v biểu thị rằng hai hòn đảo $u$ và $v$ được nối trực tiếp bằng một cây cầu.
    • Nếu $0\le u<v\le N-1$ không đúng, chương trình bị coi là Wrong Answer [3].
    • Nếu hai hòn đảo $u$ và $v$ không được nối trực tiếp bằng một cây cầu, chương trình bị coi là Wrong Answer [4].
    • Nếu gọi hàm Bridge nhiều lần với cùng các tham số u và v, chương trình bị coi là Wrong Answer [5].
    • Vì có $N-1$ cây cầu, phải gọi hàm Bridge đúng $N-1$ lần. Nếu số lần gọi hàm Bridge không phải là $N-1$ khi hàm Solve kết thúc, chương trình bị coi là Wrong Answer [6].

Lưu ý quan trọng

• Chương trình có thể cài đặt các hàm khác để dùng nội bộ hoặc sử dụng biến toàn cục.
• Chương trình không được sử dụng đầu vào chuẩn và đầu ra chuẩn. Chương trình không được giao tiếp với các tệp khác bằng bất kỳ phương thức nào. Tuy nhiên, chương trình có thể xuất thông tin gỡ lỗi ra luồng lỗi chuẩn.

Biên dịch và chạy thử

Bạn có thể tải xuống từ trang web cuộc thi một tệp nén chứa trình chấm mẫu để kiểm thử chương trình. Tệp nén cũng chứa một tệp mã nguồn mẫu cho chương trình của bạn.

Trình chấm mẫu là tệp grader.cpp. Để kiểm thử chương trình, hãy đặt grader.cpp, meetings.cpp và meetings.h trong cùng một thư mục, rồi chạy lệnh sau để biên dịch chương trình.

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

Khi biên dịch thành công, tệp thực thi grader được tạo ra.

Lưu ý rằng trình chấm thực tế khác với trình chấm mẫu. Trình chấm mẫu được thực thi dưới dạng một tiến trình duy nhất, đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn.

Dữ liệu vào cho trình chấm mẫu

Trình chấm mẫu đọc dữ liệu sau từ đầu vào chuẩn.

$$ \begin{array}{l} N\\ A_0\ B_0\\ \vdots\\ A_{N-2}\ B_{N-2} \end{array} $$

$A_i$ và $B_i$ ($0\le i\le N-2$) biểu thị rằng hai hòn đảo $A_i$ và $B_i$ được nối trực tiếp bằng một cây cầu.

Dữ liệu ra cho trình chấm mẫu

Khi chương trình kết thúc thành công, trình chấm mẫu ghi thông tin sau ra đầu ra chuẩn (dấu ngoặc kép dùng để làm rõ).

• Nếu chương trình được coi là đúng, trình chấm ghi số lần gọi hàm Query dưới dạng “Accepted: 100”.
• Nếu chương trình bị coi là Wrong Answer, trình chấm ghi loại lỗi dưới dạng “Wrong Answer [1]”.

Nếu chương trình bị coi là mắc nhiều loại Wrong Answer, trình chấm mẫu chỉ báo cáo một loại trong số đó.

Giới hạn

Xem mục “Dữ liệu vào cho trình chấm mẫu” để biết định nghĩa của $A_i$ và $B_i$.

• $3\le N\le 2\,000$.
• $0\le A_i<B_i\le N-1$ ($0\le i\le N-2$).
• Có thể đi từ bất kỳ hòn đảo nào đến bất kỳ hòn đảo nào khác qua một số cây cầu.
• Mỗi hòn đảo được nối trực tiếp với nhiều nhất 18 cây cầu.

Nhiệm vụ con

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ó giới hạn bổ sung.

5. Với các nhiệm vụ con 1, 2 và 3, nếu chương trình đúng với mọi bộ kiểm thử của một nhiệm vụ con, bạn nhận được toàn bộ số điểm của nhiệm vụ con đó.

6. Với nhiệm vụ con 4, nếu chương trình đúng với mọi bộ kiểm thử, điểm của bạn được tính như sau, trong đó $X$ là số lần gọi hàm Query lớn nhất trong một bộ kiểm thử.

   • 49 điểm nếu $40\,000<X\le 100\,000$, và
   • 71 điểm nếu $X\le 40\,000$.

Ví dụ

Dưới đây là một dữ liệu vào mẫu cho trình chấm mẫu và các lời gọi hàm tương ứng.

Dữ liệu vào 1

5
0 1
0 2
1 3
1 4

Các lời gọi mẫu

Lời gọi, lời gọi và giá trị trả về tương ứng:

Solve(5)
    Query(0, 1, 2)    0
    Query(0, 3, 4)    1
    Bridge(1, 3)      (không có)
    Bridge(0, 2)      (không có)
    Bridge(1, 4)      (không có)
    Bridge(0, 1)      (không có)