시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB99282425.806%

문제

양 손을 사용할 수 있는 박성원숭이 N마리가 나무에 매달려 있다. 1번 박성원숭이는 꼬리로 나뭇가지에 매달려 있고 다른 박성원숭이들은 다른 박성원숭이를 손에 붙들고 있거나/고 다른 박성원숭이들의 손에 붙들려 있다(붙들리면서 붙들 수도 있음). 그런데 이 박성원숭이들은 0초부터 매 초마다 어떤 박성원숭이하나가 왼손 혹은 오른손을 놓게 된다. 그렇게 되면 의지할 곳이 없는 박성원숭이들은 ‘즉시’ 바닥으로 떨어지게 된다. 우리는 각각의 박성원숭이들이 ‘언제’ 땅에 떨어지는지 알고 싶다. 물론 떨어지지 않는 박성원숭이(이를테면 1번 박성원숭이)들도 있을 수 있다.

입력

첫 줄에 박성원숭이들의 수 N(1 ≤ N ≤ 200,000)과 박성원숭이들이 손을 놓게 되는 가짓수 M(1 ≤ M ≤ 400,000)이 주어진다. 다음 N개의 줄에 걸쳐서 각 박성원숭이의 ‘왼손’에 잡혀있는 다른 박성원숭이의 번호와(없을 경우 -1) ‘오른손’에 잡혀있는 박성원숭이의 번호(없을 경우 -1)가 각각 순서대로 주어진다. 다음 M개의 줄에 걸쳐서 손을 놓는 박성원숭이의 번호와 왼손을 놓는지 오른손을 놓는지 나타내는 숫자 1(왼손) 혹은 2(오른손)가 주어진다.

출력

각 줄에 각 박성원숭이가 언제 땅에 떨어지는지 출력한다. 떨어지지 않는다면 -1을 출력한다.

예제 입력 1

3 2
-1 3
3 -1
1 2
1 2
3 1

예제 출력 1

-1
1
1

힌트

0초에 1번 박성원숭이가 오른손을 놓지만 아직 3번이 1번을 잡고 있어서 떨어지지 않고 1초에 3번  박성원숭이가 왼손을 놓게 되면서 비로소 3번과 2번이 땅에 떨어지게 된다.

W3sicHJvYmxlbV9pZCI6IjIxMDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFmMmNcdWI5YWNcdWIyZWNcdWI5YjAgXHViYzE1XHVjMTMxXHVjNmQwXHVjMjJkXHVjNzc0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1OTEgXHVjMTkwXHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMxNVx1YzEzMVx1YzZkMFx1YzIyZFx1Yzc3NCBOXHViOWM4XHViOWFjXHVhYzAwIFx1YjA5OFx1YmIzNFx1YzVkMCBcdWI5ZTRcdWIyZWNcdWI4MjQgXHVjNzg4XHViMmU0LiAxXHViYzg4IFx1YmMxNVx1YzEzMVx1YzZkMFx1YzIyZFx1Yzc3NFx1YjI5NCBcdWFmMmNcdWI5YWNcdWI4NWMgXHViMDk4XHViYjQ3XHVhYzAwXHVjOWMwXHVjNWQwIFx1YjllNFx1YjJlY1x1YjgyNCBcdWM3ODhcdWFjZTAgXHViMmU0XHViOTc4IFx1YmMxNVx1YzEzMVx1YzZkMFx1YzIyZFx1Yzc3NFx1YjRlNFx1Yzc0MCBcdWIyZTRcdWI5NzggXHViYzE1XHVjMTMxXHVjNmQwXHVjMjJkXHVjNzc0XHViOTdjIFx1YzE5MFx1YzVkMCBcdWJkOTlcdWI0ZTRcdWFjZTAgXHVjNzg4XHVhYzcwXHViMDk4XC9cdWFjZTAgXHViMmU0XHViOTc4IFx1YmMxNVx1YzEzMVx1YzZkMFx1YzIyZFx1Yzc3NFx1YjRlNFx1Yzc1OCBcdWMxOTBcdWM1ZDAgXHViZDk5XHViNGU0XHViODI0IFx1Yzc4OFx1YjJlNChcdWJkOTlcdWI0ZTRcdWI5YWNcdWJhNzRcdWMxMWMgXHViZDk5XHViNGU0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWM3NGMpLiBcdWFkZjhcdWI3ZjBcdWIzNzAgXHVjNzc0IFx1YmMxNVx1YzEzMVx1YzZkMFx1YzIyZFx1Yzc3NFx1YjRlNFx1Yzc0MCAwXHVjZDA4XHViZDgwXHVkMTMwIFx1YjllNCBcdWNkMDhcdWI5YzhcdWIyZTQgXHVjNWI0XHViNWE0IFx1YmMxNVx1YzEzMVx1YzZkMFx1YzIyZFx1Yzc3NFx1ZDU1OFx1YjA5OFx1YWMwMCBcdWM2N2NcdWMxOTAgXHVkNjM5XHVjNzQwIFx1YzYyNFx1Yjk3OFx1YzE5MFx1Yzc0NCBcdWIxOTNcdWFjOGMgXHViNDFjXHViMmU0LiBcdWFkZjhcdWI4MDdcdWFjOGMgXHViNDE4XHViYTc0IFx1Yzc1OFx1YzljMFx1ZDU2MCBcdWFjZjNcdWM3NzQgXHVjNWM2XHViMjk0IFx1YmMxNVx1YzEzMVx1YzZkMFx1YzIyZFx1Yzc3NFx1YjRlNFx1Yzc0MCAmbHNxdW87XHVjOTg5XHVjMmRjJnJzcXVvOyBcdWJjMTRcdWIyZTVcdWM3M2NcdWI4NWMgXHViNWE4XHVjNWI0XHVjOWMwXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjNmIwXHViOWFjXHViMjk0IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWJjMTVcdWMxMzFcdWM2ZDBcdWMyMmRcdWM3NzRcdWI0ZTRcdWM3NzQgJmxzcXVvO1x1YzViOFx1YzgxYyZyc3F1bzsgXHViNTQ1XHVjNWQwIFx1YjVhOFx1YzViNFx1YzljMFx1YjI5NFx1YzljMCBcdWM1NGNcdWFjZTAgXHVjMmY2XHViMmU0LiBcdWJiM2NcdWI4NjAgXHViNWE4XHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YjI5NCBcdWJjMTVcdWMxMzFcdWM2ZDBcdWMyMmRcdWM3NzQoXHVjNzc0XHViOTdjXHVkMTRjXHViYTc0IDFcdWJjODggXHViYzE1XHVjMTMxXHVjNmQwXHVjMjJkXHVjNzc0KVx1YjRlNFx1YjNjNCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHViYzE1XHVjMTMxXHVjNmQwXHVjMjJkXHVjNzc0XHViNGU0XHVjNzU4IFx1YzIxOCBOKDEgJmxlOyBOICZsZTsgMjAwLDAwMClcdWFjZmMgXHViYzE1XHVjMTMxXHVjNmQwXHVjMjJkXHVjNzc0XHViNGU0XHVjNzc0IFx1YzE5MFx1Yzc0NCBcdWIxOTNcdWFjOGMgXHViNDE4XHViMjk0IFx1YWMwMFx1YzlkM1x1YzIxOCBNKDEgJmxlOyBNICZsZTsgNDAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwXHVjMTFjIFx1YWMwMSBcdWJjMTVcdWMxMzFcdWM2ZDBcdWMyMmRcdWM3NzRcdWM3NTggJmxzcXVvO1x1YzY3Y1x1YzE5MCZyc3F1bztcdWM1ZDAgXHVjN2ExXHVkNjAwXHVjNzg4XHViMjk0IFx1YjJlNFx1Yjk3OCBcdWJjMTVcdWMxMzFcdWM2ZDBcdWMyMmRcdWM3NzRcdWM3NTggXHViYzg4XHVkNjM4XHVjNjQwKFx1YzVjNlx1Yzc0NCBcdWFjYmRcdWM2YjAgLTEpICZsc3F1bztcdWM2MjRcdWI5NzhcdWMxOTAmcnNxdW87XHVjNWQwIFx1YzdhMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWJjMTVcdWMxMzFcdWM2ZDBcdWMyMmRcdWM3NzRcdWM3NTggXHViYzg4XHVkNjM4KFx1YzVjNlx1Yzc0NCBcdWFjYmRcdWM2YjAgLTEpXHVhYzAwIFx1YWMwMVx1YWMwMSBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwXHVjMTFjIFx1YzE5MFx1Yzc0NCBcdWIxOTNcdWIyOTQgXHViYzE1XHVjMTMxXHVjNmQwXHVjMjJkXHVjNzc0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YzY0MCBcdWM2N2NcdWMxOTBcdWM3NDQgXHViMTkzXHViMjk0XHVjOWMwIFx1YzYyNFx1Yjk3OFx1YzE5MFx1Yzc0NCBcdWIxOTNcdWIyOTRcdWM5YzAgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzIyYlx1Yzc5MCAxKFx1YzY3Y1x1YzE5MCkgXHVkNjM5XHVjNzQwIDIoXHVjNjI0XHViOTc4XHVjMTkwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1YzkwNFx1YzVkMCBcdWFjMDEgXHViYzE1XHVjMTMxXHVjNmQwXHVjMjJkXHVjNzc0XHVhYzAwIFx1YzViOFx1YzgxYyBcdWI1NDVcdWM1ZDAgXHViNWE4XHVjNWI0XHVjOWMwXHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViNWE4XHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNFx1YmE3NCAtMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjBcdWNkMDhcdWM1ZDAgMVx1YmM4OCBcdWJjMTVcdWMxMzFcdWM2ZDBcdWMyMmRcdWM3NzRcdWFjMDAgXHVjNjI0XHViOTc4XHVjMTkwXHVjNzQ0IFx1YjE5M1x1YzljMFx1YjljYyBcdWM1NDRcdWM5YzEgM1x1YmM4OFx1Yzc3NCAxXHViYzg4XHVjNzQ0IFx1YzdhMVx1YWNlMCBcdWM3ODhcdWM1YjRcdWMxMWMgXHViNWE4XHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YWNlMCAxXHVjZDA4XHVjNWQwIDNcdWJjODgmbmJzcDsgXHViYzE1XHVjMTMxXHVjNmQwXHVjMjJkXHVjNzc0XHVhYzAwIFx1YzY3Y1x1YzE5MFx1Yzc0NCBcdWIxOTNcdWFjOGMgXHViNDE4XHViYTc0XHVjMTFjIFx1YmU0NFx1Yjg1Y1x1YzE4YyAzXHViYzg4XHVhY2ZjIDJcdWJjODhcdWM3NzQgXHViNTQ1XHVjNWQwIFx1YjVhOFx1YzViNFx1YzljMFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMTA1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTW9ua2V5cyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlcmUgYXJlIG4gbW9ua2V5cyBvbiBhIHRyZWUuIFRoZXkgYXJlIG51bWJlcmVkIGZyb20gMSB0byBuLiBUaGUgbW9ua2V5IG51bWJlciAxIGNsdXRjaGVzIGEgYnJhbmNoIGJ5IGl0cyB0YWlsLiBSZW1haW5pbmcgbW9ua2V5cyBlaXRoZXIgYXJlIGhlbGQgYnkgb3RoZXIgbW9ua2V5cywgaG9sZCBvbiB0byBvdGhlciBtb25rZXlzIG9yIGJvdGguIEVhY2ggbW9ua2V5IGNhbiB1c2UgdHdvIGhhbmRzIGFuZCBjYW4gaG9sZCBhdCBtb3N0IG9uZSBvdGhlciBtb25rZXkgaW4gZWFjaCBoYW5kIChncmlwcGluZyBpdHMgdGFpbCkuIFN0YXJ0aW5nIGZyb20gdGhlIG1vbWVudCAwLCBhdCBlYWNoIHNlY29uZCBvbmUgbW9ua2V5IHJlbGVhc2VzIGl0cyBncmlwIG9mIG9uZSBoYW5kLiBUaGlzIG1heSBjYXVzZSBzb21lIG1vbmtleXMgZmFsbCBkb3duIG9udG8gdGhlIGdyb3VuZCwgd2hlcmUgdGhleSBjYW4gY29udGludWUgcmVsZWFzaW5nIHRoZWlyIGdyaXBzICh0aGUgdGltZSBvZiBmYWxsaW5nIGlzIG5lZ2xpZ2libHkgc21hbGwpLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gd2hpY2g6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+cmVhZHMgZnJvbSB0aGUgc3RhbmRhcmQgaW5wdXQgdGhlIGRlc2NyaXB0aW9uIG9mIGhvdyB0aGUgbW9ua2V5cyBob2xkIHRvZ2V0aGVyIGFuZCBpbiB3aGF0IG9yZGVyIHRoZXkgcmVsZWFzZSB0aGVpciBncmlwcyw8XC9saT5cclxuXHQ8bGk+Zm9yIGVhY2ggbW9ua2V5IGNvbXB1dGVzIHRoZSB0aW1lIGl0IGZhbGxzIGRvd24gb250byB0aGUgZ3JvdW5kLDxcL2xpPlxyXG5cdDxsaT53cml0ZXMgdGhlIHJlc3VsdCB0byB0aGUgc3RhbmRhcmQgb3V0cHV0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgY29uc2lzdHMgb2YgdHdvIHBvc2l0aXZlIGludGVnZXJzIG4gYW5kIG0sIDEgJmxlOyBuICZsZTsgMjAwIDAwMCwgMSAmbGU7IG0gJmxlOyA0MDAgMDAwLiBUaGUgbnVtYmVyIG4gZGVub3RlcyB0aGUgbnVtYmVyIG9mIG1vbmtleXMsIGFuZCB0aGUgbnVtYmVyIG0gZGVub3RlcyB0aGUgdGltZSAoaW4gc2Vjb25kcykgd2Ugb2JzZXJ2ZSB0aGUgbW9ua2V5cy4gTmV4dCBuIGxpbmVzIGNvbnRhaW5zIHRoZSBkZXNjcmlwdGlvbiBvZiB0aGUgaW5pdGlhbCBzaXR1YXRpb24uIEluIHRoZSAoaysxKS1zdCBsaW5lICgxICZsZTsgayAmbGU7IG4pIHRoZXJlIGFyZSB0d28gaW50ZWdlcnMgZGVub3RpbmcgdGhlIG51bWJlcnMgb2YgbW9ua2V5cyB0aGF0IGFyZSBob2xkIGJ5IHRoZSBtb25rZXkgbnVtYmVyIGsuIFRoZSBmb3JtZXIgaXMgdGhlIG51bWJlciBvZiB0aGUgbW9ua2V5IHRoYXQgaXMgaG9sZCBieSB0aGUgbGVmdCBoYW5kLCBhbmQgdGhlIGxhdHRlciAtIGJ5IHRoZSByaWdodCBoYW5kLiBUaGUgbnVtYmVyIC0xIGRlbm90ZXMgdGhhdCB0aGUgbW9ua2V5JiMzOTtzIGhhbmQgaXMgZnJlZS4gVGhlIGZvbGxvd2luZyBtIGxpbmVzIGRlbm90ZSB0aGUgcmVzdWx0IG9mIHRoZSBvYnNlcnZhdGlvbiBvZiB0aGUgbW9ua2V5cy4gSW4gdGhlIGktdGggb2YgdGhvc2UgbGluZXMgKDEgJmxlOyBpICZsZTsgbSkgdGhlcmUgYXJlIHR3byBpbnRlZ2Vycy4gVGhlIGZvcm1lciBpcyB0aGUgbnVtYmVyIG9mIHRoZSBtb25rZXksIGFuZCB0aGUgbGF0dGVyIGlzIHRoZSBudW1iZXIgb2YgaXRzIGhhbmQgKDEgLSBsZWZ0LCAyIC0gcmlnaHQpIHRoZSBtb25rZXkgcmVsZWFzZXMgaXRzIGdyaXAgb2YsIGluIHRoZSBtb21lbnQgaS0xLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gc2hvdWxkIHdyaXRlIHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQgZXhhY3RseSBuIGludGVnZXJzLCBvbmUgcGVyIGxpbmUuIFRoZSBudW1iZXIgb2YgdGhlIGktdGggbGluZSBzaG91bGQgZGVub3RlIHRoZSBtb21lbnQgdGhlIGktdGggbW9ua2V5IGZlbGwgZG93biBvbnRvIHRoZSBncm91bmQsIG9yIHNob3VsZCBiZSBlcXVhbCAtMSBpZiB0aGUgbW9ua2V5IGhhcyBub3QgZmFsbGVuIGRvd24gb250byB0aGUgZ3JvdW5kIGR1cmluZyB0aGUgb2JzZXJ2YXRpb24uPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=