시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 45 10 9 20.455%

문제

양 손을 사용할 수 있는 박성원숭이 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+IiwiaGludCI6IjxwPjBcdWNkMDhcdWM1ZDAgMVx1YmM4OCBcdWJjMTVcdWMxMzFcdWM2ZDBcdWMyMmRcdWM3NzRcdWFjMDAgXHVjNjI0XHViOTc4XHVjMTkwXHVjNzQ0IFx1YjE5M1x1YzljMFx1YjljYyBcdWM1NDRcdWM5YzEgM1x1YmM4OFx1Yzc3NCAxXHViYzg4XHVjNzQ0IFx1YzdhMVx1YWNlMCBcdWM3ODhcdWM1YjRcdWMxMWMgXHViNWE4XHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YWNlMCAxXHVjZDA4XHVjNWQwIDNcdWJjODgmbmJzcDsgXHViYzE1XHVjMTMxXHVjNmQwXHVjMjJkXHVjNzc0XHVhYzAwIFx1YzY3Y1x1YzE5MFx1Yzc0NCBcdWIxOTNcdWFjOGMgXHViNDE4XHViYTc0XHVjMTFjIFx1YmU0NFx1Yjg1Y1x1YzE4YyAzXHViYzg4XHVhY2ZjIDJcdWJjODhcdWM3NzQgXHViNTQ1XHVjNWQwIFx1YjVhOFx1YzViNFx1YzljMFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIxMDUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNb25rZXlzIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBhcmUgbiBtb25rZXlzIG9uIGEgdHJlZS4gVGhleSBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIG4uIFRoZSBtb25rZXkgbnVtYmVyIDEgY2x1dGNoZXMgYSBicmFuY2ggYnkgaXRzIHRhaWwuIFJlbWFpbmluZyBtb25rZXlzIGVpdGhlciBhcmUgaGVsZCBieSBvdGhlciBtb25rZXlzLCBob2xkIG9uIHRvIG90aGVyIG1vbmtleXMgb3IgYm90aC4gRWFjaCBtb25rZXkgY2FuIHVzZSB0d28gaGFuZHMgYW5kIGNhbiBob2xkIGF0IG1vc3Qgb25lIG90aGVyIG1vbmtleSBpbiBlYWNoIGhhbmQgKGdyaXBwaW5nIGl0cyB0YWlsKS4gU3RhcnRpbmcgZnJvbSB0aGUgbW9tZW50IDAsIGF0IGVhY2ggc2Vjb25kIG9uZSBtb25rZXkgcmVsZWFzZXMgaXRzIGdyaXAgb2Ygb25lIGhhbmQuIFRoaXMgbWF5IGNhdXNlIHNvbWUgbW9ua2V5cyBmYWxsIGRvd24gb250byB0aGUgZ3JvdW5kLCB3aGVyZSB0aGV5IGNhbiBjb250aW51ZSByZWxlYXNpbmcgdGhlaXIgZ3JpcHMgKHRoZSB0aW1lIG9mIGZhbGxpbmcgaXMgbmVnbGlnaWJseSBzbWFsbCkuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB3aGljaDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5yZWFkcyBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCB0aGUgZGVzY3JpcHRpb24gb2YgaG93IHRoZSBtb25rZXlzIGhvbGQgdG9nZXRoZXIgYW5kIGluIHdoYXQgb3JkZXIgdGhleSByZWxlYXNlIHRoZWlyIGdyaXBzLDxcL2xpPlxyXG5cdDxsaT5mb3IgZWFjaCBtb25rZXkgY29tcHV0ZXMgdGhlIHRpbWUgaXQgZmFsbHMgZG93biBvbnRvIHRoZSBncm91bmQsPFwvbGk+XHJcblx0PGxpPndyaXRlcyB0aGUgcmVzdWx0IHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBpbnB1dCBjb25zaXN0cyBvZiB0d28gcG9zaXRpdmUgaW50ZWdlcnMgbiBhbmQgbSwgMSAmbGU7IG4gJmxlOyAyMDAgMDAwLCAxICZsZTsgbSAmbGU7IDQwMCAwMDAuIFRoZSBudW1iZXIgbiBkZW5vdGVzIHRoZSBudW1iZXIgb2YgbW9ua2V5cywgYW5kIHRoZSBudW1iZXIgbSBkZW5vdGVzIHRoZSB0aW1lIChpbiBzZWNvbmRzKSB3ZSBvYnNlcnZlIHRoZSBtb25rZXlzLiBOZXh0IG4gbGluZXMgY29udGFpbnMgdGhlIGRlc2NyaXB0aW9uIG9mIHRoZSBpbml0aWFsIHNpdHVhdGlvbi4gSW4gdGhlIChrKzEpLXN0IGxpbmUgKDEgJmxlOyBrICZsZTsgbikgdGhlcmUgYXJlIHR3byBpbnRlZ2VycyBkZW5vdGluZyB0aGUgbnVtYmVycyBvZiBtb25rZXlzIHRoYXQgYXJlIGhvbGQgYnkgdGhlIG1vbmtleSBudW1iZXIgay4gVGhlIGZvcm1lciBpcyB0aGUgbnVtYmVyIG9mIHRoZSBtb25rZXkgdGhhdCBpcyBob2xkIGJ5IHRoZSBsZWZ0IGhhbmQsIGFuZCB0aGUgbGF0dGVyIC0gYnkgdGhlIHJpZ2h0IGhhbmQuIFRoZSBudW1iZXIgLTEgZGVub3RlcyB0aGF0IHRoZSBtb25rZXkmIzM5O3MgaGFuZCBpcyBmcmVlLiBUaGUgZm9sbG93aW5nIG0gbGluZXMgZGVub3RlIHRoZSByZXN1bHQgb2YgdGhlIG9ic2VydmF0aW9uIG9mIHRoZSBtb25rZXlzLiBJbiB0aGUgaS10aCBvZiB0aG9zZSBsaW5lcyAoMSAmbGU7IGkgJmxlOyBtKSB0aGVyZSBhcmUgdHdvIGludGVnZXJzLiBUaGUgZm9ybWVyIGlzIHRoZSBudW1iZXIgb2YgdGhlIG1vbmtleSwgYW5kIHRoZSBsYXR0ZXIgaXMgdGhlIG51bWJlciBvZiBpdHMgaGFuZCAoMSAtIGxlZnQsIDIgLSByaWdodCkgdGhlIG1vbmtleSByZWxlYXNlcyBpdHMgZ3JpcCBvZiwgaW4gdGhlIG1vbWVudCBpLTEuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBzaG91bGQgd3JpdGUgdG8gdGhlIHN0YW5kYXJkIG91dHB1dCBleGFjdGx5IG4gaW50ZWdlcnMsIG9uZSBwZXIgbGluZS4gVGhlIG51bWJlciBvZiB0aGUgaS10aCBsaW5lIHNob3VsZCBkZW5vdGUgdGhlIG1vbWVudCB0aGUgaS10aCBtb25rZXkgZmVsbCBkb3duIG9udG8gdGhlIGdyb3VuZCwgb3Igc2hvdWxkIGJlIGVxdWFsIC0xIGlmIHRoZSBtb25rZXkgaGFzIG5vdCBmYWxsZW4gZG93biBvbnRvIHRoZSBncm91bmQgZHVyaW5nIHRoZSBvYnNlcnZhdGlvbi48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d