시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 389 71 45 21.429%

문제

민혁이는 매주 금요일마다 지수와 함께 논다. 이번 주 금요일은 지수와 민혁이가 친구가 된지 십 년이 되는 날이다. 따라서, 둘은 엄청난 게임을 하기로 결정했다. 민혁이는 바닥이 흙인 운동장을 예약했고, 지수는 조약돌 한 개를 들고 왔다.

먼저 민혁이는 운동장 바닥에 나뭇가지로 방향 그래프를 그린다. 이 그래프에서 모든 정점은 많아야 한 개의 나가는 간선(outgoing edge)를 가질 수 있다. 그 다음 민혁이는 조약돌을 한 정점 위에 올려 놓는다. 만약, 조약돌이 있는 정점에 나가는 간선이 있다면, 조약돌은 그 간선을 통해서 이동할 수 없을 때까지 계속해서 이동한다. 더 이상 이동할 수 있는 정점이 없다면, 조약돌은 그 자리에서 멈춘다. 조약돌은 그래프를 무한히 이동할 수도 있고, 방문하지 않는 정점이 있을 수도 있다.

민혁이는 지수가 게임의 규칙을 확실하게 이해했는지 알기 위해서 다음과 같은 두 가지 질문을 하려고 한다.

1 X - 조약돌을 정점 X에 놓았을 때, 조약돌이 무한히 움직이지 않는다면 조약돌이 멈추는 정점의 번호는 몇 번인가?

2 X - 정점 X에서 나가는 간선을 지운다. (항상 나가는 간선이 있는 정점만 주어진다)

민혁이의 질문이 주어졌을 때, 지수의 답변을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 그래프의 정점의 개수 N이 주어진다. (1 ≤ N ≤ 300,000)

둘째 줄에는 각 정점의 나가는 간선이 공백으로 구분되어서 주어진다. 정점의 번호는 1부터 시작하며, 나가는 간선이 없는 경우에는 0이 주어진다.

셋째 줄에는 민혁이의 질문의 수 Q가 주어진다. (1 ≤ Q ≤ 300,000)

넷째 줄부터 Q개 줄에는 문제 설명에 나온 질문 형식대로 민혁이의 질문이 주어진다.

출력

1로 시작하는 쿼리가 주어질때 마다, 조약돌이 멈추는 정점의 번호를 한 줄에 하나씩 출력한다. 만약, 어떤 정점에 멈추지 않고 무한히 이동한다면, CLKLUS를 출력한다.

예제 입력 1

3
2 3 1
7
1 1
1 2
2 1
1 2
1 1
2 2
1 2

예제 출력 1

CIKLUS
CIKLUS
1
1
2
W3sicHJvYmxlbV9pZCI6IjI4NDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5YzhcdWJlMTQiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YmJmY1x1ZDYwMVx1Yzc3NFx1YjI5NCBcdWI5ZTRcdWM4ZmMgXHVhZTA4XHVjNjk0XHVjNzdjXHViOWM4XHViMmU0IFx1YzljMFx1YzIxOFx1YzY0MCBcdWQ1NjhcdWFlZDggXHViMTdjXHViMmU0LiBcdWM3NzRcdWJjODggXHVjOGZjIFx1YWUwOFx1YzY5NFx1Yzc3Y1x1Yzc0MCBcdWM5YzBcdWMyMThcdWM2NDAgXHViYmZjXHVkNjAxXHVjNzc0XHVhYzAwIFx1Y2U1Y1x1YWQ2Y1x1YWMwMCBcdWI0MWNcdWM5YzAgXHVjMmVkIFx1YjE0NFx1Yzc3NCBcdWI0MThcdWIyOTQgXHViMGEwXHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YjQ1OFx1Yzc0MCBcdWM1YzRcdWNjYWRcdWIwOWMgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWFjYjBcdWM4MTVcdWQ1ODhcdWIyZTQuIFx1YmJmY1x1ZDYwMVx1Yzc3NFx1YjI5NCBcdWJjMTRcdWIyZTVcdWM3NzQgXHVkNzU5XHVjNzc4IFx1YzZiNFx1YjNkOVx1YzdhNVx1Yzc0NCBcdWM2MDhcdWM1N2RcdWQ1ODhcdWFjZTAsIFx1YzljMFx1YzIxOFx1YjI5NCBcdWM4NzBcdWM1N2RcdWIzY2MgXHVkNTVjIFx1YWMxY1x1Yjk3YyBcdWI0ZTRcdWFjZTAgXHVjNjU0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWJhM2NcdWM4MDAgXHViYmZjXHVkNjAxXHVjNzc0XHViMjk0IFx1YzZiNFx1YjNkOVx1YzdhNSBcdWJjMTRcdWIyZTVcdWM1ZDAgXHViMDk4XHViYjQ3XHVhYzAwXHVjOWMwXHViODVjIFx1YmMyOVx1ZDVhNSBcdWFkZjhcdWI3OThcdWQ1MDRcdWI5N2MgXHVhZGY4XHViOWIwXHViMmU0LiBcdWM3NzQgXHVhZGY4XHViNzk4XHVkNTA0XHVjNWQwXHVjMTFjIFx1YmFhOFx1YjRlMCBcdWM4MTVcdWM4MTBcdWM3NDAgXHViOWNlXHVjNTQ0XHVjNTdjIFx1ZDU1YyBcdWFjMWNcdWM3NTggXHViMDk4XHVhYzAwXHViMjk0IFx1YWMwNFx1YzEyMChvdXRnb2luZyBlZGdlKVx1Yjk3YyBcdWFjMDBcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWJiZmNcdWQ2MDFcdWM3NzRcdWIyOTQgXHVjODcwXHVjNTdkXHViM2NjXHVjNzQ0IFx1ZDU1YyBcdWM4MTVcdWM4MTAgXHVjNzA0XHVjNWQwIFx1YzYyY1x1YjgyNCBcdWIxOTNcdWIyOTRcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVjODcwXHVjNTdkXHViM2NjXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWM4MTBcdWM1ZDAgXHViMDk4XHVhYzAwXHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1Yzg3MFx1YzU3ZFx1YjNjY1x1Yzc0MCBcdWFkZjggXHVhYzA0XHVjMTIwXHVjNzQ0IFx1ZDFiNVx1ZDU3NFx1YzExYyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1Yzc0NCBcdWI1NGNcdWFlNGNcdWM5YzAgXHVhY2M0XHVjMThkXHVkNTc0XHVjMTFjIFx1Yzc3NFx1YjNkOVx1ZDU1Y1x1YjJlNC4gXHViMzU0IFx1Yzc3NFx1YzBjMSBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWM4MTBcdWM3NzQgXHVjNWM2XHViMmU0XHViYTc0LCBcdWM4NzBcdWM1N2RcdWIzY2NcdWM3NDAgXHVhZGY4IFx1Yzc5MFx1YjlhY1x1YzVkMFx1YzExYyBcdWJhNDhcdWNkOThcdWIyZTQuIFx1Yzg3MFx1YzU3ZFx1YjNjY1x1Yzc0MCBcdWFkZjhcdWI3OThcdWQ1MDRcdWI5N2MgXHViYjM0XHVkNTVjXHVkNzg4IFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHVhY2UwLCBcdWJjMjlcdWJiMzhcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YzgxNVx1YzgxMFx1Yzc3NCBcdWM3ODhcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViYmZjXHVkNjAxXHVjNzc0XHViMjk0IFx1YzljMFx1YzIxOFx1YWMwMCBcdWFjOGNcdWM3ODRcdWM3NTggXHVhZGRjXHVjZTU5XHVjNzQ0IFx1ZDY1NVx1YzJlNFx1ZDU1OFx1YWM4YyBcdWM3NzRcdWQ1NzRcdWQ1ODhcdWIyOTRcdWM5YzAgXHVjNTRjXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YjQ1MCBcdWFjMDBcdWM5YzAgXHVjOWM4XHViYjM4XHVjNzQ0IFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDEgWCAtIFx1Yzg3MFx1YzU3ZFx1YjNjY1x1Yzc0NCBcdWM4MTVcdWM4MTAgWFx1YzVkMCBcdWIxOTNcdWM1NThcdWM3NDQgXHViNTRjLCBcdWM4NzBcdWM1N2RcdWIzY2NcdWM3NzQgXHViYjM0XHVkNTVjXHVkNzg4IFx1YzZjMFx1YzljMVx1Yzc3NFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTRcdWJhNzQgXHVjODcwXHVjNTdkXHViM2NjXHVjNzc0IFx1YmE0OFx1Y2Q5NFx1YjI5NCBcdWM4MTVcdWM4MTBcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IFx1YmE4NyBcdWJjODhcdWM3NzhcdWFjMDA/PFwvcD5cclxuXHJcbjxwPlxyXG5cdDIgWCAtIFx1YzgxNVx1YzgxMCBYXHVjNWQwXHVjMTFjIFx1YjA5OFx1YWMwMFx1YjI5NCBcdWFjMDRcdWMxMjBcdWM3NDQgXHVjOWMwXHVjNmI0XHViMmU0LiAoXHVkNTZkXHVjMGMxIFx1YjA5OFx1YWMwMFx1YjI5NCBcdWFjMDRcdWMxMjBcdWM3NzQgXHVjNzg4XHViMjk0IFx1YzgxNVx1YzgxMFx1YjljYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmJmY1x1ZDYwMVx1Yzc3NFx1Yzc1OCBcdWM5YzhcdWJiMzhcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjOWMwXHVjMjE4XHVjNzU4IFx1YjJmNVx1YmNjMFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDMwMCwwMDApPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWIwOThcdWFjMDBcdWIyOTQgXHVhYzA0XHVjMTIwXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjRcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM4MTVcdWM4MTBcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IDFcdWJkODBcdWQxMzAgXHVjMmRjXHVjNzkxXHVkNTU4XHViYTcwLCBcdWIwOThcdWFjMDBcdWIyOTQgXHVhYzA0XHVjMTIwXHVjNzc0IFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYmZjXHVkNjAxXHVjNzc0XHVjNzU4IFx1YzljOFx1YmIzOFx1Yzc1OCBcdWMyMTggUVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgUSAmbGU7IDMwMCwwMDApPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjEzN1x1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgUVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYjM4XHVjODFjIFx1YzEyNFx1YmE4NVx1YzVkMCBcdWIwOThcdWM2MjggXHVjOWM4XHViYjM4IFx1ZDYxNVx1YzJkZFx1YjMwMFx1Yjg1YyBcdWJiZmNcdWQ2MDFcdWM3NzRcdWM3NTggXHVjOWM4XHViYjM4XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHQxXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWNmZmNcdWI5YWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4XHViNTRjIFx1YjljOFx1YjJlNCwgXHVjODcwXHVjNTdkXHViM2NjXHVjNzc0IFx1YmE0OFx1Y2Q5NFx1YjI5NCBcdWM4MTVcdWM4MTBcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWM1YjRcdWI1YTQgXHVjODE1XHVjODEwXHVjNWQwIFx1YmE0OFx1Y2Q5NFx1YzljMCBcdWM1NGFcdWFjZTAgXHViYjM0XHVkNTVjXHVkNzg4IFx1Yzc3NFx1YjNkOVx1ZDU1Y1x1YjJlNFx1YmE3NCwgQ0xLTFVTXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODQzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS1VHTElDRSIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gYW5kIFNsYXZrbyBsb3ZlIHBsYXlpbmcgd2l0aCBtYXJibGVzLiBPbiBhbiBleGNpdGluZyBGcmlkYXksIE1pcmtvIGhhcyBjb21lIHVwIHdpdGggYSBtYXJibGUgZ2FtZSB3aGljaCBoZSB3YW50cyB0byBzaG93IHRvIFNsYXZrby48XC9wPlxyXG5cclxuPHA+SW4gdGhlIGdhbWUsIE1pcmtvIGNvbnN0cnVjdHMgYSBkaXJlY3Rpb25hbCBncmFwaCBpbiB3aGljaCBhbGwgdmVydGljZXMgaGF2ZSBhdCBtb3N0IGF0IG1vc3Qgb25lIG91dGdvaW5nIGVkZ2UuIFRoZW4gaGUgcGxhY2VzIGEgbWFyYmxlIG9uIG9uZSBvZiB0aGUgdmVydGljZXMuIFdoZW5ldmVyIGEgbWFyYmxlIGlzIG9uIHNvbWUgdmVydGV4IFgsIHRoZSBtYXJibGUgbW92ZXMgdG8gdGhlIGFkamFjZW50IHZlcnRleCBjb25uZWN0ZWQgYnkgYSBzaW5nbGUgZWRnZSwgaWYgc3VjaCBleGlzdHMuIFRoZSBtb3ZlbWVudCBvZiB0aGUgbWFyYmxlIGNvbnRpbnVlcyB1bnRpbCBhIHZlcnRleCB3aXRoIG5vIG91dGdvaW5nIGVkZ2UgaXMgdmlzaXRlZCwgd2hlcmUgdGhlIG1hcmJsZSBzdG9wcy4gSXQgaXMgYWxzbyBwb3NzaWJsZSB0aGF0IHRoZSBtYXJibGUgdHJhdmVyc2VzIHRoZSBncmFwaCBpbmRlZmluaXRlbHkgaW4gY2FzZSBubyBzdWNoIHZlcnRleCBpcyBldmVyIHZpc2l0ZWQuPFwvcD5cclxuXHJcbjxwPlRvIG1ha2Ugc3VyZSB0aGF0IFNsYXZrbyB1bmRlcnN0YW5kIHRoZSBydWxlcyBvZiB0aGUgZ2FtZSwgTWlya28gd2lsbCBhc2sgYSBzZXJpZXMgb2YgcXVlcmllcy4gVGhlIHR5cGVzIG9mIHF1ZXJpZXMgYXJlIGFzIGZvbGxvd3M6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSBYICZuZGFzaDsgdW5sZXNzIHRoZSBtYXJibGUgc3R1Y2tzIGluIGEgbG9vcCwgb24gd2hpY2ggdmVydGV4IHdpbGwgdGhlIG1hcmJsZSBzdG9wIGlmIGl0IGlzIHBsYWNlZCBvbiB0aGUgdmVydGV4IFg/PFwvbGk+XHJcblx0PGxpPjIgWCAmbmRhc2g7IGRlbGV0ZSB0aGUgb3V0Z29pbmcgZWRnZSBvZiB0aGUgdmVydGV4IFggKGl0IGlzIGd1YXJhbnRlZWQgdGhhdCBzdWNoIGVkZ2Ugd2lsbCBhbHdheXMgZXhpc3QpJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Tm90ZTogcXVlcmllcyBhcmUgZXhlY3V0ZWQgaW4gb3JkZXIgYW5kIGFyZSBjdW1tdWxhdGl2ZSAob25lIGFmZmVjdHMgYW5vdGhlcikuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhIHBvc3RpdmUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDMwMCAwMDApLCB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIGluIHRoZSBncmFwaC48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIGV4YWN0bHkgTiBwb3NpdGl2ZSBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UsIHdoZXJlIHRoZSBudW1iZXIgYXQgcG9zaXRpb24gaSBkZW5vdGVzIHRoZSBpbmRleCBvZiB0aGUgZGVzdGluYXRpb24gb2YgdGhlIG91dGdvaW5nIGVkZ2UgZnJvbSB2ZXJ0ZXggd2l0aCBpbmRleCBpLiBUaGUgemVybyB2YWx1ZSByZXByZXNlbnQgdGhhdCB0aGVyZSBpcyBubyBvdXRnb2luZyBlZGdlIGZyb20gdGhlIHZlcnRleCB3aXRoIGluZGV4IGkuPFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgbGluZSBjb250YWlucyBhIHNpbmdsZSBwb3NpdGl2ZSBpbnRlZ2VyIFEgKDEgJmxlOyBRICZsZTsgMzAwIDAwMCksIHRoZSBudW1iZXIgb2YgcXVlcmllcy48XC9wPlxyXG5cclxuPHA+VGhlIHJlbWFpbmluZyBRIGxpbmVzIGNvbnRhaW4gcXVlcmllcyBpbiB0aGUgZm9ybWF0IGRlc2NyaWJlZCBhYm92ZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBxdWVyeSBvZiB0eXBlIDEsIG91dHB1dCB0aGUgaW5kZXggb2YgdGhlIHZlcnRleCB3aGVyZSB0aGUgbWFyYmxlIHN0b3BzLCBvbmUgcGVyIGxpbmUsIGluIHRoZSBvcmRlciBvZiB0aGUgZXhlY3V0aW9uIG9mIHF1ZXJpZXMuIElmIHRoZSBtYXJibGUgbmV2ZXIgc3RvcHMsIG91dHB1dCBDSUtMVVMgaW5zdGVhZC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=