시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 64 18 17 27.869%

문제

양 손을 사용할 수 있는 박성원숭이 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번이 땅에 떨어지게 된다.

W3sicHJvYmxlbV9pZCI6IjIxMDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFmMmNcdWI5YWNcdWIyZWNcdWI5YjAgXHViYzE1XHVjMTMxXHVjNmQwXHVjMjJkXHVjNzc0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1OTEgXHVjMTkwXHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMxNVx1YzEzMVx1YzZkMFx1YzIyZFx1Yzc3NCBOXHViOWM4XHViOWFjXHVhYzAwIFx1YjA5OFx1YmIzNFx1YzVkMCBcdWI5ZTRcdWIyZWNcdWI4MjQgXHVjNzg4XHViMmU0LiAxXHViYzg4IFx1YmMxNVx1YzEzMVx1YzZkMFx1YzIyZFx1Yzc3NFx1YjI5NCBcdWFmMmNcdWI5YWNcdWI4NWMgXHViMDk4XHViYjQ3XHVhYzAwXHVjOWMwXHVjNWQwIFx1YjllNFx1YjJlY1x1YjgyNCBcdWM3ODhcdWFjZTAgXHViMmU0XHViOTc4IFx1YmMxNVx1YzEzMVx1YzZkMFx1YzIyZFx1Yzc3NFx1YjRlNFx1Yzc0MCBcdWIyZTRcdWI5NzggXHViYzE1XHVjMTMxXHVjNmQwXHVjMjJkXHVjNzc0XHViOTdjIFx1YzE5MFx1YzVkMCBcdWJkOTlcdWI0ZTRcdWFjZTAgXHVjNzg4XHVhYzcwXHViMDk4XC9cdWFjZTAgXHViMmU0XHViOTc4IFx1YmMxNVx1YzEzMVx1YzZkMFx1YzIyZFx1Yzc3NFx1YjRlNFx1Yzc1OCBcdWMxOTBcdWM1ZDAgXHViZDk5XHViNGU0XHViODI0IFx1Yzc4OFx1YjJlNChcdWJkOTlcdWI0ZTRcdWI5YWNcdWJhNzRcdWMxMWMgXHViZDk5XHViNGU0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWM3NGMpLiBcdWFkZjhcdWI3ZjBcdWIzNzAgXHVjNzc0IFx1YmMxNVx1YzEzMVx1YzZkMFx1YzIyZFx1Yzc3NFx1YjRlNFx1Yzc0MCAwXHVjZDA4XHViZDgwXHVkMTMwIFx1YjllNCBcdWNkMDhcdWI5YzhcdWIyZTQgXHVjNWI0XHViNWE0IFx1YmMxNVx1YzEzMVx1YzZkMFx1YzIyZFx1Yzc3NFx1ZDU1OFx1YjA5OFx1YWMwMCBcdWM2N2NcdWMxOTAgXHVkNjM5XHVjNzQwIFx1YzYyNFx1Yjk3OFx1YzE5MFx1Yzc0NCBcdWIxOTNcdWFjOGMgXHViNDFjXHViMmU0LiBcdWFkZjhcdWI4MDdcdWFjOGMgXHViNDE4XHViYTc0IFx1Yzc1OFx1YzljMFx1ZDU2MCBcdWFjZjNcdWM3NzQgXHVjNWM2XHViMjk0IFx1YmMxNVx1YzEzMVx1YzZkMFx1YzIyZFx1Yzc3NFx1YjRlNFx1Yzc0MCAmbHNxdW87XHVjOTg5XHVjMmRjJnJzcXVvOyBcdWJjMTRcdWIyZTVcdWM3M2NcdWI4NWMgXHViNWE4XHVjNWI0XHVjOWMwXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjNmIwXHViOWFjXHViMjk0IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWJjMTVcdWMxMzFcdWM2ZDBcdWMyMmRcdWM3NzRcdWI0ZTRcdWM3NzQgJmxzcXVvO1x1YzViOFx1YzgxYyZyc3F1bzsgXHViNTQ1XHVjNWQwIFx1YjVhOFx1YzViNFx1YzljMFx1YjI5NFx1YzljMCBcdWM1NGNcdWFjZTAgXHVjMmY2XHViMmU0LiBcdWJiM2NcdWI4NjAgXHViNWE4XHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YjI5NCBcdWJjMTVcdWMxMzFcdWM2ZDBcdWMyMmRcdWM3NzQoXHVjNzc0XHViOTdjXHVkMTRjXHViYTc0IDFcdWJjODggXHViYzE1XHVjMTMxXHVjNmQwXHVjMjJkXHVjNzc0KVx1YjRlNFx1YjNjNCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWJjMTVcdWMxMzFcdWM2ZDBcdWMyMmRcdWM3NzRcdWI0ZTRcdWM3NTggXHVjMjE4IE4oMSZsdDs9TiZsdDs9MjAwLDAwMClcdWFjZmMgXHViYzE1XHVjMTMxXHVjNmQwXHVjMjJkXHVjNzc0XHViNGU0XHVjNzc0IFx1YzE5MFx1Yzc0NCBcdWIxOTNcdWFjOGMgXHViNDE4XHViMjk0IFx1YWMwMFx1YzlkM1x1YzIxOCBNKDEmbHQ7PU0mbHQ7PTQwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMFx1YzExYyBcdWFjMDEgXHViYzE1XHVjMTMxXHVjNmQwXHVjMjJkXHVjNzc0XHVjNzU4ICZsc3F1bztcdWM2N2NcdWMxOTAmcnNxdW87XHVjNWQwIFx1YzdhMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWIyZTRcdWI5NzggXHViYzE1XHVjMTMxXHVjNmQwXHVjMjJkXHVjNzc0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YzY0MChcdWM1YzZcdWM3NDQgXHVhY2JkXHVjNmIwIC0xKSAmbHNxdW87XHVjNjI0XHViOTc4XHVjMTkwJnJzcXVvO1x1YzVkMCBcdWM3YTFcdWQ2MDBcdWM3ODhcdWIyOTQgXHViYzE1XHVjMTMxXHVjNmQwXHVjMjJkXHVjNzc0XHVjNzU4IFx1YmM4OFx1ZDYzOChcdWM1YzZcdWM3NDQgXHVhY2JkXHVjNmIwIC0xKVx1YWMwMCBcdWFjMDFcdWFjMDEgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMFx1YzExYyBcdWMxOTBcdWM3NDQgXHViMTkzXHViMjk0IFx1YmMxNVx1YzEzMVx1YzZkMFx1YzIyZFx1Yzc3NFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWM2NDAgXHVjNjdjXHVjMTkwXHVjNzQ0IFx1YjE5M1x1YjI5NFx1YzljMCBcdWM2MjRcdWI5NzhcdWMxOTBcdWM3NDQgXHViMTkzXHViMjk0XHVjOWMwIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWMyMmJcdWM3OTAgMShcdWM2N2NcdWMxOTApIFx1ZDYzOVx1Yzc0MCAyKFx1YzYyNFx1Yjk3OFx1YzE5MClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiA8XC9wPiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1YmMxNVx1YzEzMVx1YzZkMFx1YzIyZFx1Yzc3NFx1YWMwMCBcdWM1YjhcdWM4MWMgXHViNTQ1XHVjNWQwIFx1YjVhOFx1YzViNFx1YzljMFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjVhOFx1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTRcdWJhNzQgLTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+IiwiaGludCI6IjxwPjBcdWNkMDhcdWM1ZDAgMVx1YmM4OCBcdWJjMTVcdWMxMzFcdWM2ZDBcdWMyMmRcdWM3NzRcdWFjMDAgXHVjNjI0XHViOTc4XHVjMTkwXHVjNzQ0IFx1YjE5M1x1YzljMFx1YjljYyBcdWM1NDRcdWM5YzEgM1x1YmM4OFx1Yzc3NCAxXHViYzg4XHVjNzQ0IFx1YzdhMVx1YWNlMCBcdWM3ODhcdWM1YjRcdWMxMWMgXHViNWE4XHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YWNlMCAxXHVjZDA4XHVjNWQwIDNcdWJjODgmbmJzcDsgXHViYzE1XHVjMTMxXHVjNmQwXHVjMjJkXHVjNzc0XHVhYzAwIFx1YzY3Y1x1YzE5MFx1Yzc0NCBcdWIxOTNcdWFjOGMgXHViNDE4XHViYTc0XHVjMTFjIFx1YmU0NFx1Yjg1Y1x1YzE4YyAzXHViYzg4XHVhY2ZjIDJcdWJjODhcdWM3NzQgXHViNTQ1XHVjNWQwIFx1YjVhOFx1YzViNFx1YzljMFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjEwNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1vbmtleXMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGFyZSBuIG1vbmtleXMgb24gYSB0cmVlLiBUaGV5IGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gbi4gVGhlIG1vbmtleSBudW1iZXIgMSBjbHV0Y2hlcyBhIGJyYW5jaCBieSBpdHMgdGFpbC4gUmVtYWluaW5nIG1vbmtleXMgZWl0aGVyIGFyZSBoZWxkIGJ5IG90aGVyIG1vbmtleXMsIGhvbGQgb24gdG8gb3RoZXIgbW9ua2V5cyBvciBib3RoLiBFYWNoIG1vbmtleSBjYW4gdXNlIHR3byBoYW5kcyBhbmQgY2FuIGhvbGQgYXQgbW9zdCBvbmUgb3RoZXIgbW9ua2V5IGluIGVhY2ggaGFuZCAoZ3JpcHBpbmcgaXRzIHRhaWwpLiBTdGFydGluZyBmcm9tIHRoZSBtb21lbnQgMCwgYXQgZWFjaCBzZWNvbmQgb25lIG1vbmtleSByZWxlYXNlcyBpdHMgZ3JpcCBvZiBvbmUgaGFuZC4gVGhpcyBtYXkgY2F1c2Ugc29tZSBtb25rZXlzIGZhbGwgZG93biBvbnRvIHRoZSBncm91bmQsIHdoZXJlIHRoZXkgY2FuIGNvbnRpbnVlIHJlbGVhc2luZyB0aGVpciBncmlwcyAodGhlIHRpbWUgb2YgZmFsbGluZyBpcyBuZWdsaWdpYmx5IHNtYWxsKS48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHdoaWNoOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnJlYWRzIGZyb20gdGhlIHN0YW5kYXJkIGlucHV0IHRoZSBkZXNjcmlwdGlvbiBvZiBob3cgdGhlIG1vbmtleXMgaG9sZCB0b2dldGhlciBhbmQgaW4gd2hhdCBvcmRlciB0aGV5IHJlbGVhc2UgdGhlaXIgZ3JpcHMsPFwvbGk+XHJcblx0PGxpPmZvciBlYWNoIG1vbmtleSBjb21wdXRlcyB0aGUgdGltZSBpdCBmYWxscyBkb3duIG9udG8gdGhlIGdyb3VuZCw8XC9saT5cclxuXHQ8bGk+d3JpdGVzIHRoZSByZXN1bHQgdG8gdGhlIHN0YW5kYXJkIG91dHB1dC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIHN0YW5kYXJkIGlucHV0IGNvbnNpc3RzIG9mIHR3byBwb3NpdGl2ZSBpbnRlZ2VycyBuIGFuZCBtLCAxICZsZTsgbiAmbGU7IDIwMCAwMDAsIDEgJmxlOyBtICZsZTsgNDAwIDAwMC4gVGhlIG51bWJlciBuIGRlbm90ZXMgdGhlIG51bWJlciBvZiBtb25rZXlzLCBhbmQgdGhlIG51bWJlciBtIGRlbm90ZXMgdGhlIHRpbWUgKGluIHNlY29uZHMpIHdlIG9ic2VydmUgdGhlIG1vbmtleXMuIE5leHQgbiBsaW5lcyBjb250YWlucyB0aGUgZGVzY3JpcHRpb24gb2YgdGhlIGluaXRpYWwgc2l0dWF0aW9uLiBJbiB0aGUgKGsrMSktc3QgbGluZSAoMSAmbGU7IGsgJmxlOyBuKSB0aGVyZSBhcmUgdHdvIGludGVnZXJzIGRlbm90aW5nIHRoZSBudW1iZXJzIG9mIG1vbmtleXMgdGhhdCBhcmUgaG9sZCBieSB0aGUgbW9ua2V5IG51bWJlciBrLiBUaGUgZm9ybWVyIGlzIHRoZSBudW1iZXIgb2YgdGhlIG1vbmtleSB0aGF0IGlzIGhvbGQgYnkgdGhlIGxlZnQgaGFuZCwgYW5kIHRoZSBsYXR0ZXIgLSBieSB0aGUgcmlnaHQgaGFuZC4gVGhlIG51bWJlciAtMSBkZW5vdGVzIHRoYXQgdGhlIG1vbmtleSYjMzk7cyBoYW5kIGlzIGZyZWUuIFRoZSBmb2xsb3dpbmcgbSBsaW5lcyBkZW5vdGUgdGhlIHJlc3VsdCBvZiB0aGUgb2JzZXJ2YXRpb24gb2YgdGhlIG1vbmtleXMuIEluIHRoZSBpLXRoIG9mIHRob3NlIGxpbmVzICgxICZsZTsgaSAmbGU7IG0pIHRoZXJlIGFyZSB0d28gaW50ZWdlcnMuIFRoZSBmb3JtZXIgaXMgdGhlIG51bWJlciBvZiB0aGUgbW9ua2V5LCBhbmQgdGhlIGxhdHRlciBpcyB0aGUgbnVtYmVyIG9mIGl0cyBoYW5kICgxIC0gbGVmdCwgMiAtIHJpZ2h0KSB0aGUgbW9ua2V5IHJlbGVhc2VzIGl0cyBncmlwIG9mLCBpbiB0aGUgbW9tZW50IGktMS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIHNob3VsZCB3cml0ZSB0byB0aGUgc3RhbmRhcmQgb3V0cHV0IGV4YWN0bHkgbiBpbnRlZ2Vycywgb25lIHBlciBsaW5lLiBUaGUgbnVtYmVyIG9mIHRoZSBpLXRoIGxpbmUgc2hvdWxkIGRlbm90ZSB0aGUgbW9tZW50IHRoZSBpLXRoIG1vbmtleSBmZWxsIGRvd24gb250byB0aGUgZ3JvdW5kLCBvciBzaG91bGQgYmUgZXF1YWwgLTEgaWYgdGhlIG1vbmtleSBoYXMgbm90IGZhbGxlbiBkb3duIG9udG8gdGhlIGdyb3VuZCBkdXJpbmcgdGhlIG9ic2VydmF0aW9uLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==