Masala #LNOQGKXVXH

Dilshod va Qodir o'yin o'ynashmoqchi. Bu safar ularda \(n\) ta tugundan iborat bog'langan siklsiz graf, ya'ni daraxt bor. Daraxtning ba'zi tugunlari qizil, qolganlari esa ko'k rangga bo'yalgan.

No'malum usul orqali, o'yinni boshlash uchun boshlang'ich tugun tanlanadi va u yerga o'yin fishka qo'yiladi. Bundan so'ng o'yinchilar navbatma navbat quyidagi amallarni bajaradi:

• O'yinchi hozirda fishka turgan tugunga ulangan hamda oldin bloklanmagan qirra tanlaydi. Agar qirrani tanlashning imkoni bo'lmasa, o'yin o'z yakuniga yetadi;
• O'yinchi qirradan foydalanib, fishkani qo'shni tugunga olib qo'yishni yoki fishkani joyida qoldirishni tanlaydi;
• Tanlangan qirra bloklanadi. E'tibor bering bloklangan qirralardan boshqa foydalanish mumkin emas. 

O'yin yakunida, Fishka qizil rangli tugunda qolsa, Dilshod yutadi, ko'k rangli tugunda qolsa, Qodir yutadi. O'yin doimo Dilshodning navbati bilan boshlanadi. Ikkala o'yinchi ham optimal o'ynaydi.

Hozirda Dilshod o'yin qaysi tugunlardan boshlansa, u g'olib bo'lishini bilmoqchi. Buni hisoblash uchun unga yordam bering.

Birincha qatorda bitta butun son - \(n(1 \leq n \leq 10 ^ 5)\), daraxtdagi tugunlar soni kiritiladi.

Ikkinchi qatorda \(n\) ta butun sondan iborat, 1 va 2 sonlaridan massiv kiritiladi. Massivning \(i\)-elementi 1 bo'lsa, \(i\)-tugun ko'k rangga, aks olda \(i\)-tugun qizil rangga bo'yalganligi anglatiladi.

Keyingi \(n-1\) ta qatorning har birida qirralarni ifodalovchi \(u\) va \(v\) sonlari kiritiladi. 

Birinchi qatorda bitta butun son, agar o'yin shu tugundan boshlansa, Dilshod yutadigan tugunlar sonini chiqaring. Bu son \(k\) bo'lsin.

Ikkinchi qatorda \(k\) ta butun son, shu tugunlarning raqamlarini chiqaring. Tugunlarni o'sish tartibida chiqarishingiz lozim.