Ini adalah soal interaktif multi-tahap (multi-pass). Ingatlah untuk melakukan flush pada buffer keluaran setelah setiap pencetakan. Untuk melakukan flush pada keluaran, Anda dapat menggunakan:

• fflush(stdout) atau cout.flush() di C/C++;
• System.out.flush() di Java dan Kotlin;
• sys.stdout.flush() di Python.

Konsep permainan, diilustrasikan oleh ChatGPT.

Dalam permainan pencocokan daring (online matching) klasik, sisi-sisi dari sebuah graf diungkapkan satu demi satu. Setiap kali sebuah sisi ditampilkan, Anda harus segera dan tidak dapat diubah lagi memutuskan apakah akan memasukkannya ke dalam pencocokan (matching) Anda. Tujuan Anda adalah memastikan tidak ada dua sisi terpilih yang berbagi titik sudut yang sama sembari memaksimalkan total banyaknya sisi yang dipilih.

Anda adalah seorang ilmuwan komputer yang ambisius dan haus akan ketenaran. Seperti yang Anda ketahui dengan baik, menemukan pencocokan maksimum dalam pengaturan daring terbukti mustahil dengan probabilitas tinggi — bahkan untuk kelas graf paling sederhana seperti graf bipartit. Namun di tempat orang lain melihat penghalang mendasar, Anda melihat peluang menuju kejayaan. Hari ini, Anda mengklaim telah memecahkan masalah terbuka yang telah lama ada untuk graf pohon dan siap memperkenalkan algoritme terobosan Anda kepada dunia.

Hanya ada satu masalah: kemarin, Anda menemukan bug dalam bukti Anda, dan Anda masih belum tahu cara memperbaikinya. Karena enggan meninggalkan sorotan panggung, Anda memutuskan untuk mengubah demonstrasi Anda menjadi pertunjukan sulap — asisten Anda, yang bersembunyi di belakang panggung, akan mengirimkan sedikit petunjuk tentang keseluruhan pohon dengan $n$ titik sudut sebelum permainan dimulai.

Rencana awal Anda sederhana: meminta asisten mengirimkan jawaban untuk setiap kueri sisi secara langsung. Untuk itu, Anda telah memasang alat dengar rahasia yang mampu menerima satu string biner sepanjang $(n - 1)$. Namun para penonton skeptis terhadap "terobosan" Anda. Untuk mencegah trik yang telah diatur sebelumnya, mereka menuntut agar sisi-sisi disajikan dalam urutan acak seragam — urutan yang tidak dapat diprediksi maupun dikendalikan baik oleh Anda maupun asisten Anda.

Panggung telah siap. Lampu sorot mengarah kepada Anda. Sekarang buktikan klaim Anda — tanpa mengganti saluran.

Protokol Interaksi

Solusi Anda dijalankan dua kali pada setiap pengujian. Pada babak prepare, solusi Anda akan berperan sebagai asisten. Pada babak play, solusi Anda akan berperan sebagai Anda, sang pesulap. Di kedua babak tersebut, solusi Anda akan dievaluasi sebagai prosedur interaktif.

Babak Persiapan (Prepare Round)

Baris pertama masukan berisi kata prepare. Baris kedua berisi sebuah bilangan bulat $n$ ($2 \le n \le 500$) — banyaknya titik sudut. $(n - 1)$ baris berikutnya masing-masing berisi dua bilangan bulat $u$ dan $v$ ($1 \le u, v \le n$, $u < v$), yang menyatakan sebuah sisi tak berarah antara $u$ dan $v$ di dalam pohon.

Anda harus mengeluarkan satu baris berisi sebuah string biner $s$ dengan panjang tepat $(n - 1)$ yang hanya terdiri atas karakter 0 dan 1. Ini adalah string yang dikirimkan ke babak play kedua. Jika keluaran Anda tidak sesuai dengan format yang diinginkan, Anda akan mendapatkan vonis Wrong Answer.

Babak Bermain (Play Round)

Solusi Anda akan dijalankan ulang untuk babak play.

Baris pertama berisi kata play. Baris kedua berisi bilangan bulat $n$. Baris ketiga berisi string biner $s$ persis seperti yang Anda cetak pada babak prepare.

Setelah itu, permainan dimulai dengan $(n - 1)$ giliran. Pada setiap giliran, satu baris berisi dua bilangan bulat $u$ dan $v$ ($1 \le u, v \le n$, $u < v$) akan diberikan. Sebagai respons, Anda harus mengeluarkan satu baris berisi take atau ignore. Semua sisi pada babak pertama akan diberikan tepat satu kali, dan urutan sisi dipilih secara acak seragam dari $(n - 1)!$ kemungkinan permutasi.

Apabila terdapat keluaran dengan format yang tidak valid, permainan akan segera berakhir tanpa informasi lebih lanjut dari interaktor.

Evaluasi Kebenaran

Misalkan $M$ adalah himpunan sisi yang diambil oleh solusi Anda. Solusi dianggap dapat diterima jika tidak ada titik sudut yang bersisian dengan lebih dari satu sisi yang diambil dan $|M| = |M^*|$, dengan $M^*$ adalah pencocokan maksimum dari graf tersebut.

Terdapat tepat $50$ pengujian, tidak termasuk pengujian contoh. Untuk lulus dari soal ini, solusi Anda harus benar pada semua pengujian, termasuk pengujian contoh.

Semua pengacakan dijamin telah ditetapkan sebelum menerima keluaran solusi. Keacakan ditetapkan untuk setiap pengujian, yang diimplementasikan dengan menetapkan seed dari pembangkit bilangan acak semu.

Sebuah alat penguji disediakan untuk membantu Anda mengembangkan dan menguji solusi Anda.

Contoh

Contoh 1, Tahap 1

Masukan

prepare
3
1 2
1 3

Keluaran

00

Contoh 1, Tahap 2

Masukan

play
3
00
1 3

1 2

Keluaran

take

ignore

Penjelasan Contoh 1

Karena $|M^*| = 1$, mengambil sisi mana pun dapat diterima, dan petunjuknya boleh sembarang.