Apakah Anda mengenal perusahaan Just Ordinary Inventions? Kegiatan perusahaan ini adalah membuat “penemuan yang biasa saja”.

JOI sedang memainkan gim terbaru yang dikembangkan oleh Just Ordinary Inventions.

Gim ini mengharuskan pemain menjelajahi sebuah dungeon yang terdiri atas beberapa ruangan dan beberapa jalan. Setiap jalan menghubungkan dua ruangan berbeda di dalam dungeon dan dapat dilalui ke kedua arah. Untuk setiap dua ruangan berbeda, terdapat paling banyak satu jalan yang menghubungkannya, dan tidak ada jalan yang kedua ujungnya berada di ruangan yang sama. Diketahui pula bahwa setiap dua ruangan di dungeon dapat saling dicapai dengan melewati beberapa jalan. Semua ruangan tampak sangat mirip; ruangan-ruangan dengan jumlah jalan keluar yang sama sama sekali tidak dapat dibedakan hanya dengan melihat tampilannya.

Dalam gim ini, setiap ruangan dilengkapi penanda dan alas untuk membantu pemain. Jalan-jalan yang keluar dari ruangan dapat diberi nomor pertama, kedua, dan seterusnya berdasarkan penanda tersebut. Struktur dungeon tidak berubah selama gim berlangsung. Jadi, jika pemain berangkat dari ruangan yang sama melalui jalan bernomor sama, ia selalu tiba di ruangan yang sama. Pada alas terdapat satu permata yang warnanya dapat diubah pemain. Warna permata adalah salah satu dari warna $1$, warna $2$, $\ldots$, warna $X$; pada awal gim, permata di setiap ruangan berwarna $1$. Warna permata tidak berubah kecuali pemain mengubahnya.

JOI menyadari bahwa jika ia mengetahui struktur dungeon, yaitu bagaimana ruangan-ruangannya dihubungkan oleh jalan, gim ini akan mudah diselesaikan. Namun, meskipun telah mencoba berbagai cara, JOI tidak berhasil menentukan struktur dungeon. Karena itu, Anda memutuskan menulis program untuk menentukan struktur dungeon sebagai pengganti JOI.

Tugas

Tulislah program yang menjelajahi dungeon dan menentukan strukturnya. Namun, JOI tidak ingin seluruh struktur dungeon diungkapkan, sehingga program tidak boleh langsung menjawab dengan struktur dungeon. Sebagai gantinya, untuk setiap bilangan bulat $i$ dari $1$ sampai $R$, program harus menjawab “berapa banyak pasangan dua ruangan yang jumlah minimum jalan untuk berpindah di antara keduanya tepat $i$” (menukar urutan kedua ruangan dianggap sebagai pasangan yang sama).

Untuk menjelajahi dungeon, Anda diberikan pustaka untuk melakukan tindakan-tindakan berikut.

• Mengetahui jumlah jalan yang keluar dari ruangan saat ini.
• Mengetahui warna permata pada alas di ruangan saat ini.
• Mengubah warna permata pada alas di ruangan saat ini menjadi warna yang ditentukan (boleh menentukan warna yang sama dengan warna saat ini). Setelah itu, memilih satu jalan keluar dari ruangan dan melewatinya menuju ruangan lain.
• Mengetahui nomor jalan yang terakhir dilalui di antara jalan-jalan yang keluar dari ruangan saat ini.

Detail Implementasi

Anda harus menulis satu program yang mengimplementasikan cara memberikan jawaban kepada JOI. Program harus menyertakan dungeon2.h.

Program harus mengimplementasikan rutin berikut.

• void Inspect(int R)

  Rutin ini dipanggil tepat satu kali pada awal.

  • Argumen R menyatakan bahwa, untuk setiap bilangan bulat $i$ dari $1$ sampai $R$, Anda harus menjawab “berapa banyak pasangan dua ruangan yang jumlah minimum jalan untuk berpindah di antara keduanya tepat $i$” (menukar urutan kedua ruangan dianggap sebagai pasangan yang sama).

Selain itu, Anda harus memanggil rutin berikut untuk memberikan jawaban.

• void Answer(int D, int A)

  • Argumen D dan A menyatakan bahwa pemanggilan ini menjawab “ada $A$ pasangan dua ruangan yang jumlah minimum jalan untuk berpindah di antara keduanya tepat $D$”.

  Pemanggilan Answer harus memenuhi syarat-syarat berikut.

  • D harus merupakan bilangan bulat dari $1$ sampai $R$. Jika tidak, hasilnya adalah Jawaban Salah [1].
  • Answer tidak boleh dipanggil dua kali atau lebih dengan argumen D yang sama. Jika tidak, hasilnya adalah Jawaban Salah [2].
  • Answer harus dipanggil tepat $R$ kali. Jika tidak, hasilnya adalah Jawaban Salah [3].
  • A harus sama dengan jumlah pasangan dua ruangan yang jumlah minimum jalan untuk berpindah di antara keduanya tepat $D$. Jika tidak, hasilnya adalah Jawaban Salah [4].

  Jika pemanggilan Answer dinilai salah, tidak ada jaminan bahwa program akan terus dijalankan setelahnya.

Selain itu, program dapat memanggil rutin-rutin berikut.

• void Move(int I, int C)

  • Argumen I adalah nomor jalan yang dipilih pemain untuk berpindah. Segera setelah pemanggilan ini, pemain berpindah ke ruangan lain melalui jalan ke-$I$ yang keluar dari ruangan saat ini.
  • Argumen C menyatakan bahwa, sebelum berpindah ruangan, warna permata pada alas di ruangan saat ini diubah menjadi warna $C$.

  Pemanggilan Move harus memenuhi syarat-syarat berikut.

  • Jika jumlah jalan yang keluar dari ruangan saat ini adalah $K$, argumen I harus merupakan bilangan bulat dari $1$ sampai $K$. Jika tidak, hasilnya adalah Jawaban Salah [5].
  • Jika jumlah warna permata adalah $X$, argumen C harus merupakan bilangan bulat dari $1$ sampai $X$. Nilai $X$ ditentukan untuk setiap subsoal. Jika tidak, hasilnya adalah Jawaban Salah [6].
  • Move tidak boleh dipanggil lebih dari $1\,500\,000$ kali. Jika dipanggil lebih banyak, hasilnya adalah Jawaban Salah [7].

• int NumberOfRoads()

  • Fungsi ini mengembalikan jumlah jalan yang keluar dari ruangan tempat pemain berada saat ini.

• int LastRoad()

  • Fungsi ini mengembalikan nomor jalan yang terakhir dilalui pemain di antara jalan-jalan yang keluar dari ruangan saat ini. Namun, jika fungsi ini dipanggil sebelum Move pernah dipanggil, fungsi mengembalikan -1.

• int Color()

  • Fungsi ini mengembalikan warna permata pada alas di ruangan tempat pemain berada saat ini.

Setelah rutin Inspect dipanggil, jawaban akan dinilai.

Anda bebas mengimplementasikan rutin lain untuk penggunaan internal atau mendeklarasikan variabel global. Namun, program yang dikumpulkan tidak boleh berinteraksi dengan masukan standar, keluaran standar, ataupun berkas lain dengan cara apa pun.

Kompilasi dan Eksekusi

Contoh program penilai untuk menguji program Anda terdapat dalam arsip yang dapat diunduh dari situs kontes. Arsip ini juga memuat contoh berkas yang harus dikumpulkan.

Contoh program penilai terdiri atas satu berkas, yaitu grader.c atau grader.cpp. Untuk menguji program Anda, jalankan perintah berikut.

• Untuk C:

  gcc -std=c11 -O2 -o grader grader.c dungeon2.c -lm

• Untuk C++:

  g++ -std=c++11 -O2 -o grader grader.cpp dungeon2.cpp

Jika kompilasi berhasil, berkas eksekusi bernama grader akan dibuat.

Perhatikan bahwa program penilai sebenarnya berbeda dari contoh program penilai. Contoh program penilai berjalan sebagai satu proses. Program ini membaca masukan dari masukan standar dan menulis hasil ke keluaran standar.

Masukan Contoh Program Penilai

Contoh program penilai membaca data berikut dari masukan standar.

• Baris pertama berisi bilangan bulat $N,X,R$ yang dipisahkan spasi. Ini menyatakan bahwa dungeon memiliki $N$ ruangan, yaitu ruangan $1$, ruangan $2$, $\ldots$, ruangan $N$, tersedia $X$ warna permata, dan program harus memberikan $R$ nilai jawaban.
• Baris ke-$2i-1$ ($1\le i\le N$) dari $2N$ baris berikutnya berisi bilangan bulat $D_i$, yang menyatakan bahwa ada $D_i$ jalan keluar dari ruangan $i$. Baris ke-$2i$ ($1\le i\le N$) berisi $D_i$ bilangan bulat $T_{i1},T_{i2},\ldots,T_{iD_i}$ yang dipisahkan spasi. Ini menyatakan bahwa jika pemain berpindah melalui jalan ke-$j$ ($1\le j\le D_i$) dari ruangan $i$, ia tiba di ruangan $T_{ij}$.
• Baris ke-$j$ ($1\le j\le R$) dari $R$ baris berikutnya berisi bilangan bulat $A_j$. Ini menyatakan bahwa ada $A_j$ pasangan dua ruangan yang jumlah minimum jalan untuk berpindah di antara keduanya tepat $j$. Dengan kata lain, untuk setiap $j$ ($1\le j\le R$), contoh program penilai menganggap jawaban benar jika Answer dipanggil dengan argumen D bernilai $j$ dan argumen A bernilai $A_j$, dan menganggap jawaban salah dalam kasus lainnya.

Contoh program penilai memanggil rutin yang Anda buat dengan posisi awal pemain di ruangan $1$.

Keluaran Contoh Program Penilai

Jika eksekusi program berakhir secara normal, contoh program penilai menulis informasi berikut dalam satu baris ke keluaran standar (tanda kutip tidak benar-benar dicetak).

• Jika jawaban benar, jumlah pemanggilan fungsi Move dicetak seperti “Accepted : #move = 8”.
• Jika jawaban salah, jenis kesalahan dicetak seperti “Wrong Answer [1]”.

Batasan

Semua data masukan memenuhi syarat-syarat berikut. Untuk arti $N,D_i,T_{ij}$, lihat bagian “Masukan Contoh Program Penilai”.

• $2\le N\le 200$.
• $3\le X\le 100$.
• $1\le R\le 200$.
• $1\le D_i\le N-1$ ($1\le i\le N$).
• $1\le T_{ij}\le N$ dan $T_{ij}\ne i$ ($1\le i\le N$, $1\le j\le D_i$).
• $T_{i1},T_{i2},\ldots,T_{iD_i}$ ($1\le i\le N$) semuanya berbeda satu sama lain.
• Untuk setiap $i,j$ ($1\le i\le N$, $1\le j\le D_i$), terdapat $k$ ($1\le k\le D_{T_{ij}}$) yang memenuhi $T_{T_{ij}k}=i$.
• Setiap dua ruangan dapat saling dicapai dengan melewati beberapa jalan.

Subsoal

Pada bagian berikut, $N$ menyatakan jumlah ruangan dan $M$ menyatakan jumlah jalan di dungeon dalam data masukan.

Subsoal 1 [17 poin]

Syarat-syarat berikut berlaku.

• $N\le 50$.
• $M\le 100$.
• $X=100$.

Subsoal 2 [27 poin]

Syarat-syarat berikut berlaku.

• $N\le 50$.
• $M\le 100$.
• $X=3$.

Subsoal 3 [56 poin]

• Berlaku $X=3$.

Pada subsoal ini, nilai ditentukan sebagai berikut.

• Misalkan $L$ adalah nilai maksimum dari nilai berikut di antara seluruh kasus uji dalam subsoal ini.

  • $\frac{C}{M}$, dengan $C$ menyatakan jumlah pemanggilan Move.

• Nilai untuk subsoal ini adalah:

  • 56 poin jika $L\le 14$.
  • $\lfloor70-L\rfloor$ poin jika $14<L\le32$.
  • $\left\lfloor54-\frac{L}{2}\right\rfloor$ poin jika $32<L\le64$.
  • 0 poin jika $64<L$.

Di sini, $\lfloor x\rfloor$ menyatakan bilangan bulat terbesar yang tidak melebihi $x$.

Dalam sistem penilaian, jika program berakhir dengan benar dan jawabannya dinilai benar, kolom detail akan menampilkan Accepted. Namun, perhatikan bahwa dalam penilaian subsoal 3, untuk kasus uji dengan $C,M$ di atas yang memenuhi $64<\frac{C}{M}$, kolom hasil akan menampilkan Jawaban Salah.

Contoh Interaksi

Berikut contoh masukan yang dibaca oleh contoh program penilai beserta contoh pemanggilan rutin yang bersesuaian.

Masukan 1

4 3 3
1
2
3
1 3 4
2
2 4
2
2 3
4
2
0

Contoh Pemanggilan Rutin

Perhatikan bahwa pemanggilan fungsi dalam contoh ini belum tentu merupakan pemanggilan yang bermakna.