Girlianda
시간 제한1초메모리 제한1024 MB
나무 모양으로 연결된 전구들에서 매초 꺼진 이웃이 하나라도 있으면 꺼지고 아니면 켜지는데, 모두 꺼지는 최초 시각을 구하거나 -1을 출력한다.
문제
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