Hvalevrijedan Hitac

Ovogodišnju Noć vještica nećemo pamtiti po impresivno izrezbarenim bundevama ili razuzdanim tulumima. Nažalost, pamtit ćemo je po odlasku Seana Connerya, poznatog škotskog glumca koji je prvi utjelovio lik Jamesa Bonda. Dakako, ova je vijest odjeknula svijetom te su se mnoge slavne osobe od ovog velikana oprostile putem društvenih mreža. Tako je Pierce Brosnan izjavio da je za njega Sean Connery najbolji James Bond, a Josip Manolić se pomalo našalio rekavši da mu je najteže kada kolege špijuni odlaze mladi. Zanimljivo, gospodin Malnar nije se oglasio na svom Facebook profilu, već je istog trena posegnuo za videokasetom svog najdražeg filma. Dakako, radi se o filmu Nedodirljivi iz 1987. u kojem lik Seana Connerya izgovara poznatu rečenicu – “Never bring a knife to a gunfight.”.

Gospodin Malnar je zbog svojih vještina bacanja noževa oduvijek bio sumnjičav prema toj tvrdnji te je odlučio provjeriti njenu istinitost postavivši mete na stablo koje mu se nalazi u dvorištu. Brzo je odredio da se stablo sastoji od n čvorova te je u svaki čvor stabla odlučio postaviti jednu metu. Mete je izradio sam, bile su kružnog oblika te je jedna strana mete bila obojena u zelenu, a druga u crvenu boju. Nakon što je postavio mete u čvorove stabla, krenuo ih je gađati noževima.

Ubrzo je primijetio da je nepogrešiv, odnosno, savršenom će preciznošću pogoditi upravo onu metu koju je gađao. Dodatno, zbog siline hitca ta će meta biti potpuno uništena, a mete koje se nalaze na susjednim čvorovima toj meti će se zaokrenuti te, iz perspektive gospodina Malnara, promijeniti boju. Oduševljen ovom činjenicom, gospodin Malnar osmislio je sljedeću igru:

• Na početku igre u svakom se čvoru stabla nalazi meta.
• Gospodin Malnar jednim hitcem smije pogoditi neku od meta koje su, iz njegove perspektive, obojene zelenom bojom. Sukladno prethodnom odlomku, pogođena meta će biti uništena, a njoj susjedne mete će promijeniti boju.
• Cilj igre je uništiti sve mete koje se nalaze na stablu.

Vaš je zadatak odrediti može li gospodin Malnar pobijediti u ovoj igri. Ako može, potrebno je dodatno odrediti bilo koji redoslijed hitaca kako bi mu to pošlo za rukom.

Napomena: Dvije su mete susjedne ako se nalaze u čvorovima koji su direktno spojeni bridom.

U prvom je retku prirodan broj n (1 ≤ n ≤ 200 000) iz teksta zadatka.

U drugom je retku n brojeva odvojenih razmacima koji predstavljaju boje meta koje se nalaze u čvorovima stabla. Preciznije, i-ti broj u drugom retku je 1 ako gospodin Malnar u i-tom čvoru vidi metu zelene boje, odnosno 0 ako u tom čvoru vidi metu crvene boje.

U sljedećih se n − 1 redaka nalaze po dva prirodna broja a i b (1 ≤ a, b ≤ n) koji predstavljaju brid između čvorova a i b. Bridovi su takvi da čine stablo, jednostavan povezan graf bez ciklusa.

U prvi redak ispišite riječ POBJEDA ako gospodin Malnar može pobijediti u igri, odnosno PORAZ ako to ne može.

U slučaju da je pobjeda moguća, u drugom je retku potrebno ispisati n prirodnih brojeva koji redom označavaju hitce gospodina Malnara. Odnosno, i-ti ispisani broj treba predstavljati oznaku čvora u kojem se nalazi meta koju će gospodin Malnar uništiti i-tim hitcem.