Egy parkban azt látjuk, hogy $N$ majom közül az 1-es számú egy nagyon nagy fa egyik ágába kapaszkodik a farkával. A majmok a kezükkel kapcsolódhatnak más majmokhoz úgy, hogy egy majom egy másik lábát fogja. Így tarthatnak más majmokat azáltal, hogy beléjük kapaszkodnak, vagy úgy, hogy beléjük kapaszkodnak más majmok. Egy majom lábába bárhány majom kapaszkodhat. Szeretnénk végezni egy $M$ másodpercig tartó vizsgálatot, amelynél minden másodpercben egy majom szabaddá teszi adott kezét, vagyis elengedi egy másik majom lábát, ha eddig fogta azt. A program számítsa ki, hogy mikor esnek le az egyes majmok a földre. Egy majom akkor esik le, ha az 1-es számú majom nem tartja közvetett, vagy közvetlen módon.
A standard bemenet első sorában a majmok $1\le N\le 200000$ száma és a vizsgálat ideje $1\le M\le 400000$ másodperc található, a következő $N$ sor mindegyikében két szám ($b_i$ és $j_i$), amely megadja, hogy az $i$-edik majom a bal és a jobb kezével hányadik majomba kapaszkodik. Amennyiben valamelyik szám $-1$, az azt jelenti, hogy azzal a kezével senkibe sem kapaszkodik, azzal a kezével senkit sem tart. A standard bemenet következő $M$ sorában az $x_j$, $y_j$ egészek megmutatják, hogy a $j$-edik másodpercben az $x_j$-edik majom az $y_j$-edik kezével elengedi a fogást (1. kéz a bal, 2. kéz a jobb). A program írja a standard output $N$ sorába a majmok földet érésének idejét. Az $i$-edik sorba az $i$-edik majom földet érésének ideje kerüljön, és $-1$, ha nem ér földet a vizsgált időintervallum végéig.