Girlianda

Linas dovanų gavo neįprastą girliandą. Ši girlianda sudaryta iš N tarpusavyje sujungtų lempučių. Visos lemputės yra sujungtos į vieną bendrą tinklą, o tinkle ciklų nėra. Tiesiogiai sujungtas lemputes vadinsime kaimyninėmis.

Pradiniu momentu, t.y. įjungus girliandą į elektros tinklą (t = 0), kai kurios lemputės šviečia, o kai kurios – ne. Tuomet, kiekvieną sekundę įjungtų lempučių konfigūracija keičiasi. Laiko momentu t kiekviena lemputė yra arba įjungiama, arba išjungiama pagal tokią taisyklę:

• Lemputė nešvies, jeigu t − 1 momentu ji turėjo bent vieną kaimyninę lemputę, kuri nešvietė;
• Kitu atveju, lemputė švies.

Linui parūpo sužinoti, per kiek sekundžių po įjungimo į elektros tinklą visos girliandos lemputės užges.

Pirmoje eilutėje pateikiamas vienas sveikasis skaičius N – girliandos lempučių kiekis.

Antroje eilutėje pateikta N − 1 sveikųjų skaičių pi (2 ≤ i ≤ N, pi < i). Skaičius pi nusako, kad i-toji lemputė yra prijungta prie pi-tosios.

Trečioje eilutėje pateikta N sveikųjų skaičių si (1 ≤ i ≤ N). Jei si = 1, lemputė i nuliniu laiko momentu šviečia, o jei si = 0 — nešviečia.

Išveskite vieną sveikąjį skaičių – mažiausią sekundžių kiekį, po kurio visos girliandos lemputės bus išjungtos. Jeigu taip niekada neįvyks, išveskite −1.

• 2 ≤ N ≤ 500 000