Di banyak tempat di Rusia, salju turun pada musim dingin. Rusia memiliki $N$ kota yang diberi nomor dari $0$ hingga $N-1$. Terdapat $N-1$ jalan yang diberi nomor dari $0$ hingga $N-2$. Jalan $i$ ($0 \le i \le N-2$) menghubungkan dua kota berbeda $A_i,B_i$ ($0 \le A_i<B_i \le N-1$) secara dua arah. Setiap dua kota berbeda di Rusia dapat saling dicapai melalui sejumlah jalan.

Keadaan turunnya salju pada setiap jalan berubah dari hari ke hari. Pada hari apa pun, di setiap jalan salju sedang turun atau tidak sedang turun. Keadaan ini tidak berubah selama satu hari.

Anya dan Boris bekerja di dinas perhubungan Rusia. Anya berada di bagian pengelolaan informasi jalan, sedangkan Boris berada di bagian yang menjawab pertanyaan warga. Pertanyaan warga adalah berapa paling sedikit jalan yang sedang bersalju yang harus dilalui untuk bepergian dari kota $0$, ibu kota Rusia, ke suatu kota lain. Biasanya, setelah menerima pertanyaan, Boris berkomunikasi dengan Anya lalu menjawab warga tersebut.

Kini, kejuaraan dunia pemrograman akan diselenggarakan di Rusia selama $Q$ hari. Selama kejuaraan, jalur komunikasi diperkirakan padat sehingga Anya dan Boris sulit berkomunikasi secara langsung. Oleh karena itu, mereka memutuskan untuk berkomunikasi dengan cara berikut.

• Pada awal setiap hari, Anya menerima informasi turunnya salju hari itu dan mengirimkan data ke server perantara.
• Ketika Boris menerima pertanyaan warga, ia menjawabnya dengan berkomunikasi dengan server perantara.

Namun, komunikasi Anya dan Boris memiliki batasan berikut.

• Kapasitas server perantara adalah $L=1\,000$ bit. Anya hanya dapat menyimpan paling banyak $L$ bit informasi di server perantara.
• Semua data di server perantara diinisialisasi menjadi $0$ pada awal setiap hari.
• Dalam satu kali komunikasi dengan server perantara, Boris dapat membaca satu bit informasi yang ia tentukan.
• Untuk menjawab setiap pertanyaan, Boris dapat berkomunikasi dengan server perantara paling banyak 20 kali.

Anda mengenal kepala dinas perhubungan, sehingga Anda diminta memikirkan strategi Anya dan Boris.

Tugas

Buatlah program yang mengimplementasikan strategi Anya dan Boris agar dapat menjawab pertanyaan warga dengan benar.

Detail Implementasi

Anda harus mengirimkan dua berkas yang ditulis dalam bahasa pemrograman yang sama.

Berkas pertama bernama Anya.c atau Anya.cpp. Berkas ini mengimplementasikan strategi Anya dan harus mengimplementasikan dua rutin berikut. Program harus menyertakan Anyalib.h.

• void InitAnya(int N, int A[], int B[])

  Fungsi ini dipanggil tepat sekali pada setiap kasus uji.

  • Argumen N menyatakan jumlah kota.
  • Argumen A[] dan B[] masing-masing merupakan larik sepanjang $N-1$ yang menyatakan sambungan jalan. Elemen A[i] dan B[i] ($0 \le i \le N-2$) adalah bilangan bulat yang menyatakan bahwa jalan $i$ menghubungkan kota A[i] dan B[i] secara dua arah, dan memenuhi $0 \le A[i]<B[i] \le N-1$.

• void Anya(int C[])

  Fungsi ini dipanggil $Q$ kali setelah InitAnya dipanggil. Fungsi ini sesuai dengan tindakan Anya menentukan deretan bit yang disimpan di server perantara setelah informasi turunnya salju diperbarui pada awal hari.

  • Argumen C[] adalah larik sepanjang $N-1$ yang menyatakan informasi turunnya salju pada jalan. Elemen C[i] ($0 \le i \le N-2$) adalah bilangan bulat $0$ atau $1$ yang menyatakan informasi salju pada jalan $i$: $C[i]=1$ berarti salju turun pada jalan $i$, sedangkan $C[i]=0$ berarti salju tidak turun pada jalan $i$.

Dalam fungsi Anya, Anda boleh memanggil fungsi berikut.

• void Save(int place, int bit)

  Fungsi ini menyatakan operasi Anya menyimpan satu bit di server perantara.

  • Argumen place menyatakan lokasi bit yang akan ditulis. place harus merupakan bilangan bulat dari $0$ hingga $L-1$, inklusif. Pemanggilan dengan nilai di luar rentang ini menghasilkan penilaian Wrong Answer [1]. Dalam setiap pemanggilan fungsi Anya, fungsi ini tidak boleh dipanggil dua kali atau lebih dengan argumen place yang sama. Jika dipanggil dua kali dengan argumen yang sama, hasilnya Wrong Answer [2].
  • Argumen bit adalah bilangan bulat yang menyatakan bit yang akan ditulis dan harus bernilai $0$ atau $1$. Pemanggilan dengan nilai lain menghasilkan Wrong Answer [3].

Setelah Save dipanggil, isi bit ke-place di server perantara menjadi bit.

Jika pemanggilan Save dinilai salah, program segera dihentikan.

Tepat sebelum fungsi Anya dipanggil, semua bit server perantara selalu diinisialisasi menjadi $0$. Dengan demikian, ketika fungsi Anya selesai, lokasi yang tidak ditulisi melalui fungsi Save berisi $0$.

Berkas kedua bernama Boris.c atau Boris.cpp. Berkas ini mengimplementasikan strategi Boris dan harus mengimplementasikan dua rutin berikut. Program harus menyertakan Borislib.h.

• void InitBoris(int N, int A[], int B[])

  Fungsi ini dipanggil tepat sekali pada setiap kasus uji.

  • Argumen N menyatakan jumlah kota.
  • Argumen A[] dan B[] masing-masing merupakan larik sepanjang $N-1$ yang menyatakan sambungan jalan. Elemen A[i] dan B[i] ($0 \le i \le N-2$) adalah bilangan bulat yang menyatakan bahwa jalan $i$ menghubungkan kota A[i] dan B[i] secara dua arah, dan memenuhi $0 \le A[i]<B[i] \le N-1$.

• int Boris(int city)

  Fungsi ini dipanggil beberapa kali setelah InitBoris dipanggil. Fungsi ini sesuai dengan tindakan Boris dalam menjawab pertanyaan warga.

  • Argumen city menyatakan pertanyaan warga. city adalah bilangan bulat dari $1$ hingga $N-1$, inklusif. Warga menanyakan paling sedikit berapa jalan yang sedang bersalju yang harus dilalui untuk bepergian dari kota $0$ ke kota city.
  • Fungsi Boris harus mengembalikan bilangan bulat dari $0$ hingga $N-1$, inklusif, yang merupakan jawaban pertanyaan warga. Jika mengembalikan bilangan bulat di luar rentang ini, hasilnya Wrong Answer [4]. Jika jawabannya tidak benar, hasilnya Wrong Answer [7].

Dalam fungsi Boris, Anda boleh memanggil fungsi berikut.

• int Ask(int place)

  Fungsi ini menyatakan operasi Boris membaca satu bit dari server perantara.

  • Argumen place menyatakan lokasi bit yang akan dibaca. place harus merupakan bilangan bulat dari $0$ hingga $L-1$, inklusif. Pemanggilan dengan nilai di luar rentang ini menghasilkan Wrong Answer [5].

  Nilai kembalian Ask adalah bilangan bulat $0$ atau $1$ yang menyatakan isi bit ke-place pada server perantara. Dalam setiap pemanggilan fungsi Boris, fungsi Ask hanya boleh dipanggil paling banyak 20 kali. Jika dipanggil lebih dari 20 kali, hasilnya Wrong Answer [6].

Jika pemanggilan Ask dinilai salah, program segera dihentikan.

Prosedur Penilaian

Penilaian dilakukan dengan prosedur berikut. Jika dinilai salah, program langsung dihentikan saat itu juga.

1. Untuk memberikan informasi jalan, InitAnya dan InitBoris dipanggil masing-masing sekali dalam urutan tersebut.

2. Untuk $i=1,\ldots,Q$, lakukan operasi berikut secara berurutan.

   • (a) Panggil fungsi Anya tepat sekali. Ini sesuai dengan tindakan Anya menentukan deretan bit yang disimpan di server perantara setelah informasi turunnya salju diperbarui pada awal hari.
   • (b) Panggil fungsi Boris sebanyak $D_i$ kali. $D_i$ adalah jumlah pertanyaan warga pada hari ke-$i$. Argumen pada pemanggilan ke-$j$ ($1 \le j \le D_i$) adalah $R_{ij}$ ($1 \le R_{ij} \le N-1$). Jika nilai kembalian Boris pada pemanggilan ke-$j$ tidak sama dengan jumlah minimum jalan yang sedang bersalju yang harus dilalui dari kota $0$ ke kota $R_{ij}$, hasilnya dinilai salah.

3. Jika tidak pernah dinilai salah, hasilnya dinilai benar.

Catatan Penting

• Waktu eksekusi dan penggunaan memori diukur untuk langkah (1) dan (2) pada “Prosedur Penilaian”. Jika jawaban benar, pada langkah (2), Anya dipanggil total $Q$ kali dan Boris dipanggil total $D_1+\cdots+D_Q$ kali.
• Anya maupun Boris tidak dapat mengetahui nilai $D_1,\ldots,D_Q$.
• Fungsi Boris tidak diberikan informasi tentang kapan fungsi Anya memperbarui data yang tersimpan di server perantara.
• Anda bebas mengimplementasikan rutin lain untuk penggunaan internal atau mendeklarasikan variabel global. Namun, dua program yang dikirimkan akan ditautkan bersama program penilai menjadi satu berkas yang dapat dieksekusi. Karena itu, semua variabel global dan rutin internal di setiap berkas (selain InitAnya, Anya, InitBoris, Boris) harus dideklarasikan static agar tidak mengganggu berkas lain. Saat penilaian, program dijalankan sebagai dua proses, yaitu sisi Anya dan sisi Boris, sehingga variabel global program tidak dapat dibagikan antara kedua sisi.
• Kiriman Anda tidak boleh berkomunikasi dengan masukan standar, keluaran standar, maupun berkas lain dengan cara apa pun.

Cara Kompilasi dan Eksekusi

Arsip yang dapat diunduh dari situs kontes memuat program penilai contoh untuk menguji program yang Anda buat. Arsip tersebut juga memuat contoh berkas yang harus dikirimkan.

Program penilai contoh terdiri dari satu berkas, yaitu grader.c atau grader.cpp. Jika program Anda adalah Anya.c dan Boris.c, atau Anya.cpp dan Boris.cpp, jalankan perintah berikut untuk mengujinya.

• Untuk C

  gcc -std=c11 -O2 -o grader grader.c Anya.c Boris.c -lm

• Untuk C++

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

Jika kompilasi berhasil, berkas eksekusi bernama grader akan dibuat.

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

Gambaran Program Penilai Contoh

Program penilai contoh memanggil fungsi sesuai “Prosedur Penilaian”.

Perhatikan perbedaan berikut dari perilaku program penilai sebenarnya.

• Program penilai contoh tidak memeriksa Wrong Answer [7], melainkan mencetak nilai kembalian fungsi Boris untuk setiap pertanyaan.

Masukan Program Penilai Contoh

Program penilai contoh membaca data berikut dari masukan standar.

• Baris pertama berisi bilangan bulat $N$, yang menyatakan jumlah kota.
• Baris ke-$(i+1)$ ($0 \le i \le N-2$) dari $N-1$ baris berikutnya berisi bilangan bulat $A_i,B_i$ yang dipisahkan spasi. Ini menyatakan bahwa jalan $i$ menghubungkan kota $A_i$ dan $B_i$ secara dua arah.
• Baris berikutnya berisi bilangan bulat $Q$, yang menyatakan bahwa kejuaraan berlangsung selama $Q$ hari.
• Baris ke-$i$ ($1 \le i \le Q$) dari $Q$ baris berikutnya berisi string $S_i$ sepanjang $N-1$ dan $D_i+1$ bilangan bulat, semuanya dipisahkan spasi. $S_i$ menyatakan informasi salju pada hari ke-$i$. Jika karakter ke-$(j+1)$ dari kiri ($0 \le j \le N-2$) pada $S_i$ adalah 1, salju turun pada jalan $j$; jika 0, salju tidak turun pada jalan $j$. Bilangan bulat pertama dari $D_i+1$ bilangan bulat berikutnya adalah $D_i$. Kemudian terdapat $D_i$ bilangan bulat $R_{i1},\ldots,R_{iD_i}$. Ini menyatakan bahwa pada hari ke-$i$, pertanyaan ke-$j$ ($1 \le j \le D_i$) menanyakan jumlah minimum jalan yang sedang bersalju yang harus dilalui untuk bepergian dari kota $0$ ke kota $R_{ij}$.

Keluaran Program Penilai Contoh

Program penilai contoh mencetak informasi berikut ke keluaran standar (tanda kutip tidak dicetak).

• Jika program dinilai salah saat dijalankan, jenis kesalahannya dicetak seperti “Wrong Answer [1]”, lalu eksekusi dihentikan.
• Jika semua $D_i$ pemanggilan Boris setelah pemanggilan Anya ke-$i$ ($1 \le i \le Q$) tidak dinilai salah, pada saat itu dicetak satu baris berisi $D_i$ bilangan bulat yang dipisahkan spasi. Bilangan ke-$j$ ($1 \le j \le D_i$) adalah nilai kembalian Boris dengan argumen $R_{ij}$.

Jika program memenuhi beberapa kondisi jawaban salah sekaligus, hanya satu jenis kesalahan yang ditampilkan.

Batasan

Semua data masukan memenuhi kondisi berikut.

• $2 \le N \le 500$.
• $1 \le Q \le 500$.
• $0 \le A_i<B_i \le N-1$ ($0 \le i \le N-2$).
• $1 \le D_j$ ($1 \le j \le Q$).
• $D_1+\cdots+D_Q \le 500$.
• Setiap dua kota berbeda dapat saling dicapai melalui sejumlah jalan.

Subsoal

Subsoal 1 [15 poin]

• Memenuhi $N \le 20$.

Subsoal 2 [5 poin]

• Memenuhi $N \le 100$.

Subsoal 3 [35 poin]

Memenuhi kondisi berikut.

• $A_i=i$ ($0 \le i \le N-2$).
• $B_i=i+1$ ($0 \le i \le N-2$).

Subsoal 4 [45 poin]

Tidak ada batasan tambahan.

Contoh Komunikasi

Berikut contoh masukan yang dibaca program penilai contoh dan contoh pemanggilan fungsi yang bersesuaian.

Masukan 1

5
0 1
1 2
1 4
2 3
2
0101 3 2 4 3
1110 1 4

Contoh Pemanggilan Rutin

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

Argumen yang diberikan kepada InitAnya(...), InitBoris(...), serta pemanggilan pertama dan kedua Anya(...) pada contoh tersebut adalah sebagai berikut.