Terdapat $N$ pulau tempat berang-berang tinggal, bernomor dari $0$ hingga $N-1$. Pulau-pulau ini dihubungkan oleh $N-1$ jembatan dua arah. Kita dapat bepergian antara sembarang pulau dengan menggunakan beberapa jembatan. Untuk setiap pulau, terdapat paling banyak $18$ jembatan yang terhubung langsung dengannya. Setiap pulau dihuni oleh seekor berang-berang.

Terkadang, beberapa berang-berang berkumpul di sebuah pulau untuk mengadakan pertemuan. Ketika tepat tiga berang-berang bertemu, mereka berkumpul di pulau berikut:

Pulau yang meminimalkan jumlah total jembatan yang dilalui ketiga berang-berang saat berkumpul (pulau seperti ini ada dan unik).

Perhatikan bahwa pulau ini mungkin sama dengan pulau tempat salah satu dari ketiga berang-berang tinggal.

Anda tertarik untuk mengetahui bagaimana $N$ pulau tersebut terhubung oleh jembatan. Anda tidak dapat mengunjungi dan memeriksa pulau-pulau tersebut secara langsung, sehingga Anda akan memberikan beberapa instruksi kepada berang-berang. Sebuah instruksi adalah sebagai berikut:

• Anda menentukan tiga pulau $u$, $v$, dan $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$), lalu meminta berang-berang yang tinggal di pulau $u$, $v$, dan $w$ mengadakan pertemuan.
• Kemudian, Anda dapat melihat pulau tempat ketiga berang-berang berkumpul.

Anda ingin menentukan bagaimana pulau-pulau tersebut terhubung dengan sedikit instruksi.

Tulislah program yang, diberikan jumlah pulau, berkomunikasi dengan berang-berang untuk menentukan bagaimana pulau-pulau tersebut terhubung.

Detail Implementasi

Anda perlu mengumpulkan satu berkas.

Nama berkas tersebut adalah meetings.cpp. Berkas ini harus mengimplementasikan fungsi berikut. Program harus menyertakan meetings.h.

• void Solve(int N)

  Fungsi ini dipanggil tepat sekali untuk setiap kasus uji.

  • Parameter N menyatakan $N$, jumlah pulau.

  Program Anda dapat memanggil fungsi-fungsi berikut.

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

    Untuk indeks tiga pulau yang Anda tentukan, fungsi ini mengembalikan indeks pulau tempat berang-berang yang tinggal di sana berkumpul untuk mengadakan pertemuan.

    • Anda menentukan indeks ketiga pulau $u$, $v$, dan $w$ melalui parameter u, v, dan w, secara berurutan. Nilai-nilai ini harus memenuhi $0 \le u \le N-1$, $0 \le v \le N-1$, $0 \le w \le N-1$, $u \ne v$, $u \ne w$, dan $v \ne w$. Jika tidak, program Anda dinilai sebagai Jawaban Salah [1].
    • Fungsi Query tidak boleh dipanggil lebih dari $100\,000$ kali. Jika tidak, program Anda dinilai sebagai Jawaban Salah [2].

  • void Bridge(int u, int v)

    Dengan fungsi ini, Anda menjawab bagaimana pulau-pulau terhubung oleh jembatan.

    • Parameter u dan v menyatakan bahwa pulau $u$ dan $v$ terhubung langsung oleh sebuah jembatan.
    • Jika $0 \le u < v \le N-1$ tidak terpenuhi, program Anda dinilai sebagai Jawaban Salah [3].
    • Jika pulau $u$ dan $v$ tidak terhubung langsung oleh sebuah jembatan, program Anda dinilai sebagai Jawaban Salah [4].
    • Jika fungsi Bridge dipanggil beberapa kali dengan parameter u dan v yang sama, program Anda dinilai sebagai Jawaban Salah [5].
    • Karena terdapat $N-1$ jembatan, fungsi Bridge harus dipanggil tepat $N-1$ kali. Jika jumlah pemanggilan fungsi Bridge bukan $N-1$ pada akhir eksekusi fungsi Solve, program Anda dinilai sebagai Jawaban Salah [6].

Catatan Penting

• Program Anda boleh mengimplementasikan fungsi lain untuk penggunaan internal atau menggunakan variabel global.
• Program Anda tidak boleh menggunakan masukan standar maupun keluaran standar. Program Anda tidak boleh berkomunikasi dengan berkas lain dengan cara apa pun. Namun, program Anda boleh mengeluarkan informasi debug ke keluaran galat standar.

Kompilasi dan Pengujian

Anda dapat mengunduh sebuah berkas arsip dari halaman web kontes yang berisi grader contoh untuk menguji program Anda. Berkas arsip tersebut juga berisi berkas kode sumber contoh untuk program Anda.

Grader contoh adalah berkas grader.cpp. Untuk menguji program Anda, letakkan grader.cpp, meetings.cpp, dan meetings.h dalam direktori yang sama, lalu jalankan perintah berikut untuk mengompilasi program-program Anda.

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

Jika kompilasi berhasil, berkas eksekusi grader akan dihasilkan.

Perhatikan bahwa grader yang sebenarnya berbeda dari grader contoh. Grader contoh akan dijalankan sebagai satu proses yang membaca data masukan dari masukan standar dan menulis hasil ke keluaran standar.

Masukan untuk Grader Contoh

Grader contoh membaca data berikut dari masukan standar.

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

$A_i$ dan $B_i$ ($0 \le i \le N-2$) menyatakan bahwa pulau $A_i$ dan $B_i$ terhubung langsung oleh sebuah jembatan.

Keluaran untuk Grader Contoh

Ketika program berakhir dengan sukses, grader contoh menulis informasi berikut ke keluaran standar (tanda kutip digunakan untuk kejelasan).

• Jika program Anda dinilai benar, grader menulis jumlah pemanggilan fungsi Query seperti Accepted: 100.
• Jika program Anda dinilai sebagai Jawaban Salah, grader menulis jenisnya seperti Wrong Answer [1].

Jika program Anda dinilai memiliki beberapa jenis Jawaban Salah, grader contoh hanya melaporkan salah satunya.

Batasan

Lihat bagian “Masukan untuk Grader Contoh” untuk definisi $A_i$ dan $B_i$.

• $3 \le N \le 2\,000$.
• $0 \le A_i < B_i \le N-1$ ($0 \le i \le N-2$).
• Kita dapat bepergian antara sembarang pulau dengan menggunakan beberapa jembatan.
• Untuk setiap pulau, terdapat paling banyak $18$ jembatan yang terhubung langsung dengannya.

Subtugas

1. (7 poin) $N \le 7$.
2. (10 poin) $N \le 50$.
3. (12 poin) $N \le 300$.

4. (71 poin) Tidak ada batasan tambahan.

5. Untuk Subtugas 1, 2, dan 3, jika program Anda benar untuk semua kasus uji dalam suatu subtugas, Anda memperoleh nilai penuh.

6. Untuk Subtugas 4, jika program Anda benar untuk semua kasus uji, nilai Anda adalah sebagai berikut, dengan $X$ adalah jumlah maksimum pemanggilan fungsi Query untuk satu kasus uji.

   • 49 poin jika $40\,000 < X \le 100\,000$, dan
   • 71 poin jika $X \le 40\,000$.

Contoh Komunikasi

Berikut adalah contoh masukan untuk grader contoh beserta pemanggilan fungsi yang bersesuaian.

Masukan 1

5
0 1
0 2
1 3
1 4

Contoh Pemanggilan

Solve(5)
    Query(0, 1, 2) -> 0
    Query(0, 3, 4) -> 1
    Bridge(1, 3)
    Bridge(0, 2)
    Bridge(1, 4)
    Bridge(0, 1)

Keempat pemanggilan Bridge tidak mengembalikan nilai.