Di pabrik JOI Co., Ltd., terdapat $N$ meja, bernomor dari $0$ hingga $N-1$. Di pabrik tersebut terdapat $N-1$ ban berjalan, bernomor dari $0$ hingga $N-2$. Ban berjalan $i$ ($0 \le i \le N-2$) menghubungkan meja $A_i$ dan meja $B_i$. Ban tersebut mengangkut produk dari salah satu meja ke meja lainnya. Namun, arah pengangkutannya tidak dapat dilihat. Jika arah ban berjalan diabaikan, setiap pasangan meja terhubung melalui sejumlah ban berjalan.

IOI-kun adalah direktur pabrik. Karena ia lupa arah pengangkutan setiap ban berjalan, ia akan melakukan rangkaian operasi berikut beberapa kali.

1. Ia memilih sejumlah ban berjalan dan membalik arah pengangkutan ban-ban yang dipilih.
2. Ia memilih sejumlah meja dan meletakkan satu produk pada setiap meja yang dipilih.

3. Untuk setiap meja yang diletaki produk, salah satu hal berikut terjadi secara serentak.

   • Jika tidak ada ban berjalan yang mengangkut produk keluar dari meja tersebut, tidak terjadi apa-apa.
   • Jika ada ban berjalan yang mengangkut produk keluar dari meja tersebut, produk di atas meja diangkut oleh salah satu ban tersebut. Produk berhenti di meja tujuan ban berjalan itu dan tidak bergerak lagi.

4. IOI-kun memeriksa apakah terdapat satu atau lebih produk pada setiap meja. Jika suatu meja memiliki produk, IOI-kun mengambil semuanya.

5. Untuk setiap ban berjalan yang arahnya dibalik pada operasi 1, IOI-kun mengembalikan arahnya sehingga menjadi arah semula.

IOI-kun ingin menentukan arah semula setiap ban berjalan dengan melakukan rangkaian operasi di atas paling banyak 30 kali.

Diberikan informasi meja-meja yang dihubungkan oleh ban berjalan, tulislah program yang menerapkan strategi IOI-kun untuk menentukan arah semula setiap ban berjalan dengan melakukan rangkaian operasi tersebut paling banyak 30 kali.

Detail Implementasi

Anda harus mengumpulkan satu berkas.

Berkas tersebut adalah conveyor.cpp. Berkas ini harus mengimplementasikan fungsi berikut. Program harus menyertakan conveyor.h menggunakan direktif prapemrosesan #include.

Fungsi berikut harus diimplementasikan dalam conveyor.cpp.

• void Solve(int N, std::vector<int> A, std::vector<int> B)

Fungsi ini dipanggil tepat sekali untuk setiap kasus uji.

• Parameter N adalah jumlah meja $N$.
• Parameter A, B adalah larik dengan panjang $N-1$ yang menjelaskan meja-meja yang dihubungkan oleh ban berjalan.

Program Anda dapat memanggil fungsi berikut.

std::vector<int> Query(std::vector<int> x, std::vector<int> y)

Dengan fungsi ini, IOI-kun melakukan operasi-operasi di pabrik.

• Parameter x adalah larik dengan panjang $N-1$. Untuk $0 \le i \le N-2$, IOI-kun membalik arah ban berjalan $i$ jika x[i] = 1, dan tidak membaliknya jika x[i] = 0.
• Parameter y adalah larik dengan panjang $N$. Untuk $0 \le j \le N-1$, IOI-kun meletakkan satu produk pada meja $j$ jika y[j] = 1, dan tidak meletakkan produk jika y[j] = 0.
• Misalkan z adalah nilai kembalian fungsi ini. Nilai tersebut adalah larik dengan panjang $N$. Untuk $0 \le j \le N-1$, terdapat satu atau lebih produk pada meja $j$ jika z[j] = 1, dan tidak ada produk jika z[j] = 0.
• Panjang larik x harus sama dengan $N-1$. Jika syarat ini tidak dipenuhi, program Anda dinilai sebagai Wrong Answer [1].
• Setiap elemen larik x harus bernilai $0$ atau $1$. Jika syarat ini tidak dipenuhi, program Anda dinilai sebagai Wrong Answer [2].
• Panjang larik y harus sama dengan $N$. Jika syarat ini tidak dipenuhi, program Anda dinilai sebagai Wrong Answer [3].
• Setiap elemen larik y harus bernilai $0$ atau $1$. Jika syarat ini tidak dipenuhi, program Anda dinilai sebagai Wrong Answer [4].
• Fungsi Query tidak boleh dipanggil lebih dari 30 kali. Jika dipanggil lebih dari 30 kali, program Anda dinilai sebagai Wrong Answer [5].

void Answer(std::vector<int> a)

Dengan fungsi ini, IOI-kun melaporkan arah semula setiap ban berjalan.

• Parameter a adalah larik dengan panjang $N-1$. Untuk $0 \le i \le N-2$, ban berjalan $i$ mengangkut produk dari $A_i$ ke $B_i$ jika a[i] = 0, dan dari $B_i$ ke $A_i$ jika a[i] = 1.
• Panjang larik a harus sama dengan $N-1$. Jika syarat ini tidak dipenuhi, program Anda dinilai sebagai Wrong Answer [6].
• Setiap elemen larik a harus bernilai $0$ atau $1$. Jika syarat ini tidak dipenuhi, program Anda dinilai sebagai Wrong Answer [7].
• Jika IOI-kun melaporkan arah suatu ban berjalan secara salah, program Anda dinilai sebagai Wrong Answer [8].
• Fungsi Answer harus dipanggil tepat sekali. Jika dipanggil lebih dari sekali, program Anda dinilai sebagai Wrong Answer [9]. Ketika fungsi Solve berakhir, jika Answer belum dipanggil, program Anda dinilai sebagai Wrong Answer [10].

Catatan Penting

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

Kompilasi dan Pengujian

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

Penilai contoh adalah berkas grader.cpp. Untuk menguji program Anda, letakkan grader.cpp, conveyor.cpp, dan conveyor.h dalam direktori yang sama, lalu jalankan perintah berikut untuk mengompilasi program. Sebagai alternatif, Anda dapat menjalankan compile.sh yang terdapat dalam arsip.

g++ -std=gnu++17 -O2 -o grader grader.cpp conveyor.cpp

Jika kompilasi berhasil, berkas eksekutabel grader akan dihasilkan.

Perhatikan bahwa penilai sebenarnya berbeda dari penilai contoh. Penilai contoh dijalankan sebagai satu proses, yang membaca data masukan dari masukan standar dan menulis hasilnya ke keluaran standar.

Masukan untuk Penilai Contoh

Penilai contoh membaca data berikut dari masukan standar.

$$ \begin{gathered} N\\ A_0\ A_1\ \cdots\ A_{N-2}\\ B_0\ B_1\ \cdots\ B_{N-2}\\ C_0\ C_1\ \cdots\ C_{N-2} \end{gathered} $$

Untuk $0 \le i \le N-2$, berlaku $C_i=0$ jika ban berjalan $i$ mengangkut produk dari meja $A_i$ ke meja $B_i$. Jika tidak, berlaku $C_i=1$.

Keluaran Penilai Contoh

Penilai contoh mengeluarkan informasi berikut ke keluaran standar (tanda kutip digunakan untuk memperjelas).

• Jika program Anda dinilai benar, penilai melaporkan jumlah pemanggilan fungsi Query, misalnya Accepted: 22.
• Jika program Anda dinilai sebagai salah satu jenis Wrong Answer, penilai contoh menulis jenisnya, misalnya Wrong Answer [4].

Jika program Anda memenuhi syarat beberapa jenis Wrong Answer, penilai contoh hanya melaporkan salah satunya.

Pada penilai contoh, di antara ban-ban berjalan yang mengangkut produk keluar dari meja yang diletaki produk, ban yang mengangkut produk dipilih secara acak seragam menggunakan bilangan acak semu yang hasilnya tidak berubah pada eksekusi yang berbeda. Untuk mengubah benih bilangan acak semu, jalankan penilai contoh dengan argumen bilangan bulat pertama seperti berikut.

./grader 2023

Catatan Penilaian

Untuk sebagian kasus uji, penilai sebenarnya bersifat adaptif. Artinya, penilai tidak memiliki jawaban tetap sejak awal dan memberikan tanggapan berdasarkan pemanggilan fungsi Query sebelumnya. Dijamin bahwa terdapat setidaknya satu jawaban yang tidak bertentangan dengan seluruh tanggapan penilai.

Batasan

Semua data masukan memenuhi syarat berikut.

• $0 \le A_i \le N-1$ ($0 \le i \le N-2$).
• $0 \le B_i \le N-1$ ($0 \le i \le N-2$).
• Jika arah ban berjalan diabaikan, setiap pasangan meja terhubung melalui sejumlah ban berjalan.

Subsoal

1. (1 poin) $N=2$.
2. (14 poin) $N=30$.
3. (10 poin) $N=100\,000$, $A_i=i$ ($0 \le i \le N-2$), $B_i=i+1$ ($0 \le i \le N-2$).
4. (75 poin) $N=100\,000$.

Contoh

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

Masukan 1

3
0 2
2 1
1 0

Contoh Pemanggilan Fungsi

Untuk pemanggilan pertama fungsi Query, nilai kembalian lain yang mungkin adalah [0, 1, 0], selain [1, 0, 0].

Untuk pemanggilan kedua fungsi Query, produk pada meja $0$ diangkut ke meja $2$ melalui ban berjalan $0$, lalu berhenti di sana. Perhatikan bahwa produk ini tidak akan diangkut ke meja $1$ melalui ban berjalan $1$.

Perhatikan bahwa contoh masukan ini tidak memenuhi batasan subsoal mana pun.

Di antara berkas-berkas yang dapat diperoleh dari halaman web kontes, sample-02.txt memenuhi batasan Subsoal 1, dan sample-03.txt memenuhi batasan Subsoal 2.