시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 337 61 37 22.024%

문제

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

먼저 민혁이는 운동장 바닥에 나뭇가지로 방향 그래프를 그린다. 이 그래프에서 모든 정점은 많아야 한 개의 나가는 간선(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
W3sicHJvYmxlbV9pZCI6IjI4NDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5YzhcdWJlMTQiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YmJmY1x1ZDYwMVx1Yzc3NFx1YjI5NCBcdWI5ZTRcdWM4ZmMgXHVhZTA4XHVjNjk0XHVjNzdjXHViOWM4XHViMmU0IFx1YzljMFx1YzIxOFx1YzY0MCBcdWQ1NjhcdWFlZDggXHViMTdjXHViMmU0LiBcdWM3NzRcdWJjODhcdWM4ZmMgXHVhZTA4XHVjNjk0XHVjNzdjXHVjNzQwIFx1YzljMFx1YzIxOFx1YzY0MCBcdWJiZmNcdWQ2MDFcdWM3NzRcdWFjMDAgXHVjZTVjXHVhZDZjXHVhYzAwIFx1YjQxY1x1YzljMCBcdWMyZWQgXHViMTQ0XHVjNzc0IFx1YjQxOFx1YjI5NCBcdWIwYTBcdWM3NzRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHViNDU4XHVjNzQwIFx1YzVjNFx1Y2NhZFx1YjA5YyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTU4XHVhZTMwXHViODVjIFx1YWNiMFx1YzgxNVx1ZDU4OFx1YjJlNC4gXHViYmZjXHVkNjAxXHVjNzc0XHViMjk0IFx1YmMxNFx1YjJlNVx1Yzc3NCBcdWQ3NTlcdWM3NzggXHVjNmI0XHViM2Q5XHVjN2E1XHVjNzQ0IFx1YzYwOFx1YzU3ZFx1ZDU4OFx1YWNlMCwgXHVjOWMwXHVjMjE4XHViMjk0IFx1Yzg3MFx1YzU3ZFx1YjNjYyBcdWQ1NWMgXHVhYzFjXHViOTdjIFx1YjRlNFx1YWNlMCBcdWM2NTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmEzY1x1YzgwMCBcdWJiZmNcdWQ2MDFcdWM3NzRcdWIyOTQgXHVjNmI0XHViM2Q5XHVjN2E1IFx1YmMxNFx1YjJlNVx1YzVkMCBcdWIwOThcdWJiNDdcdWFjMDBcdWM5YzBcdWI4NWMgXHViYzI5XHVkNWE1IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yjk3YyBcdWFkZjhcdWI5YjBcdWIyZTQuIFx1Yzc3NCBcdWFkZjhcdWI3OThcdWQ1MDRcdWM1ZDBcdWMxMWMgXHViYWE4XHViNGUwIFx1YzgxNVx1YzgxMFx1Yzc0MCBcdWI5Y2VcdWM1NDRcdWM1N2MgXHVkNTVjIFx1YWMxY1x1Yzc1OCBcdWIwOThcdWFjMDBcdWIyOTQgXHVhYzA0XHVjMTIwKG91dGdvaW5nIGVkZ2UpXHViOTdjIFx1YWMwMFx1YzljOCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIFx1YmJmY1x1ZDYwMVx1Yzc3NFx1YjI5NCBcdWM4NzBcdWM1N2RcdWIzY2NcdWM3NDQgXHVkNTVjIFx1YzgxNVx1YzgxMCBcdWM3MDRcdWM1ZDAgXHVjNjJjXHViODI0IFx1YjE5M1x1YjI5NFx1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWM4NzBcdWM1N2RcdWIzY2NcdWM3NzQgXHVjNzg4XHViMjk0IFx1YzgxNVx1YzgxMFx1YzVkMCBcdWIwOThcdWFjMDBcdWIyOTQgXHVhYzA0XHVjMTIwXHVjNzc0IFx1Yzc4OFx1YjJlNFx1YmE3NCwgXHVjODcwXHVjNTdkXHViM2NjXHVjNzQwIFx1YWRmOCBcdWFjMDRcdWMxMjBcdWM3NDQgXHVkMWI1XHVkNTc0XHVjMTFjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHVjNzQ0IFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWFjYzRcdWMxOGRcdWQ1NzRcdWMxMWMgXHVjNzc0XHViM2Q5XHVkNTVjXHViMmU0LiBcdWIzNTQgXHVjNzc0XHVjMGMxIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzgxNVx1YzgxMFx1Yzc3NCBcdWM1YzZcdWIyZTRcdWJhNzQsIFx1Yzg3MFx1YzU3ZFx1YjNjY1x1Yzc0MCBcdWFkZjggXHVjNzkwXHViOWFjXHVjNWQwXHVjMTFjIFx1YmE0OFx1Y2Q5OFx1YjJlNC4gXHVjODcwXHVjNTdkXHViM2NjXHVjNzQwIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yjk3YyBcdWJiMzRcdWQ1NWNcdWQ3ODggXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWFjZTAsIFx1YmMyOVx1YmIzOFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVjODE1XHVjODEwXHVjNzc0IFx1Yzc4OFx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWJiZmNcdWQ2MDFcdWM3NzRcdWIyOTQgXHVjOWMwXHVjMjE4XHVhYzAwIFx1YWM4Y1x1Yzc4NFx1Yzc1OCBcdWFkZGNcdWNlNTlcdWM3NDQgXHVkNjU1XHVjMmU0XHVkNTU4XHVhYzhjIFx1Yzc3NFx1ZDU3NFx1ZDU4OFx1YjI5NFx1YzljMCBcdWM1NGNcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViNDUwIFx1YWMwMFx1YzljMCBcdWM5YzhcdWJiMzhcdWM3NDQgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0MSBYIC0gXHVjODcwXHVjNTdkXHViM2NjXHVjNzQ0IFx1YzgxNVx1YzgxMCBYXHVjNWQwIFx1YjE5M1x1YzU1OFx1Yzc0NCBcdWI1NGMsIFx1Yzg3MFx1YzU3ZFx1YjNjY1x1Yzc3NCBcdWJiMzRcdWQ1NWNcdWQ3ODggXHVjNmMwXHVjOWMxXHVjNzc0XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNFx1YmE3NCBcdWM4NzBcdWM1N2RcdWIzY2NcdWM3NzQgXHViYTQ4XHVjZDk0XHViMjk0IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgXHViYTg3IFx1YmM4OFx1Yzc3OFx1YWMwMD88XC9wPlxyXG5cclxuPHA+XHJcblx0MiBYIC0gXHVjODE1XHVjODEwIFhcdWM1ZDBcdWMxMWMgXHViMDk4XHVhYzAwXHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc0NCBcdWM5YzBcdWM2YjRcdWIyZTQuIChcdWQ1NmRcdWMwYzEgXHViMDk4XHVhYzAwXHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjODE1XHVjODEwXHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCk8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViYmZjXHVkNjAxXHVjNzc0XHVjNzU4IFx1YzljOFx1YmIzOFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM5YzBcdWMyMThcdWM3NTggXHViMmY1XHViY2MwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NTggXHVjODE1XHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMzAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjODE1XHVjODEwXHVjNzU4IFx1YjA5OFx1YWMwMFx1YjI5NCBcdWFjMDRcdWMxMjBcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgMVx1YmQ4MFx1ZDEzMCBcdWMyZGNcdWM3OTFcdWQ1NThcdWJhNzAsIFx1YjA5OFx1YWMwMFx1YjI5NCBcdWFjMDRcdWMxMjBcdWM3NzQgXHVjNWM2XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJiZmNcdWQ2MDFcdWM3NzRcdWM3NTggXHVjOWM4XHViYjM4XHVjNzU4IFx1YzIxOCBRXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBRICZsZTsgMzAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMTM3XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBRXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJiMzhcdWM4MWMgXHVjMTI0XHViYTg1XHVjNWQwIFx1YjA5OFx1YzYyOCBcdWM5YzhcdWJiMzggXHVkNjE1XHVjMmRkXHViMzAwXHViODVjIFx1YmJmY1x1ZDYwMVx1Yzc3NFx1Yzc1OCBcdWM5YzhcdWJiMzhcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdDFcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IFx1Y2ZmY1x1YjlhY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzhcdWI1NGMgXHViOWM4XHViMmU0LCBcdWM4NzBcdWM1N2RcdWIzY2NcdWM3NzQgXHViYTQ4XHVjZDk0XHViMjk0IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YzViNFx1YjVhNCBcdWM4MTVcdWM4MTBcdWM1ZDAgXHViYTQ4XHVjZDk0XHVjOWMwIFx1YzU0YVx1YWNlMCBcdWJiMzRcdWQ1NWNcdWQ3ODggXHVjNzc0XHViM2Q5XHVkNTVjXHViMmU0XHViYTc0LCBDTEtMVVNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI4NDMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJLVUdMSUNFIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBhbmQgU2xhdmtvIGxvdmUgcGxheWluZyB3aXRoIG1hcmJsZXMuIE9uIGFuIGV4Y2l0aW5nIEZyaWRheSwgTWlya28gaGFzIGNvbWUgdXAgd2l0aCBhIG1hcmJsZSBnYW1lIHdoaWNoIGhlIHdhbnRzIHRvIHNob3cgdG8gU2xhdmtvLjxcL3A+XHJcblxyXG48cD5JbiB0aGUgZ2FtZSwgTWlya28gY29uc3RydWN0cyBhIGRpcmVjdGlvbmFsIGdyYXBoIGluIHdoaWNoIGFsbCB2ZXJ0aWNlcyBoYXZlIGF0IG1vc3QgYXQgbW9zdCBvbmUgb3V0Z29pbmcgZWRnZS4gVGhlbiBoZSBwbGFjZXMgYSBtYXJibGUgb24gb25lIG9mIHRoZSB2ZXJ0aWNlcy4gV2hlbmV2ZXIgYSBtYXJibGUgaXMgb24gc29tZSB2ZXJ0ZXggWCwgdGhlIG1hcmJsZSBtb3ZlcyB0byB0aGUgYWRqYWNlbnQgdmVydGV4IGNvbm5lY3RlZCBieSBhIHNpbmdsZSBlZGdlLCBpZiBzdWNoIGV4aXN0cy4gVGhlIG1vdmVtZW50IG9mIHRoZSBtYXJibGUgY29udGludWVzIHVudGlsIGEgdmVydGV4IHdpdGggbm8gb3V0Z29pbmcgZWRnZSBpcyB2aXNpdGVkLCB3aGVyZSB0aGUgbWFyYmxlIHN0b3BzLiBJdCBpcyBhbHNvIHBvc3NpYmxlIHRoYXQgdGhlIG1hcmJsZSB0cmF2ZXJzZXMgdGhlIGdyYXBoIGluZGVmaW5pdGVseSBpbiBjYXNlIG5vIHN1Y2ggdmVydGV4IGlzIGV2ZXIgdmlzaXRlZC48XC9wPlxyXG5cclxuPHA+VG8gbWFrZSBzdXJlIHRoYXQgU2xhdmtvIHVuZGVyc3RhbmQgdGhlIHJ1bGVzIG9mIHRoZSBnYW1lLCBNaXJrbyB3aWxsIGFzayBhIHNlcmllcyBvZiBxdWVyaWVzLiBUaGUgdHlwZXMgb2YgcXVlcmllcyBhcmUgYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xIFggJm5kYXNoOyB1bmxlc3MgdGhlIG1hcmJsZSBzdHVja3MgaW4gYSBsb29wLCBvbiB3aGljaCB2ZXJ0ZXggd2lsbCB0aGUgbWFyYmxlIHN0b3AgaWYgaXQgaXMgcGxhY2VkIG9uIHRoZSB2ZXJ0ZXggWD88XC9saT5cclxuXHQ8bGk+MiBYICZuZGFzaDsgZGVsZXRlIHRoZSBvdXRnb2luZyBlZGdlIG9mIHRoZSB2ZXJ0ZXggWCAoaXQgaXMgZ3VhcmFudGVlZCB0aGF0IHN1Y2ggZWRnZSB3aWxsIGFsd2F5cyBleGlzdCkmbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Ob3RlOiBxdWVyaWVzIGFyZSBleGVjdXRlZCBpbiBvcmRlciBhbmQgYXJlIGN1bW11bGF0aXZlIChvbmUgYWZmZWN0cyBhbm90aGVyKS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGEgcG9zdGl2ZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMzAwIDAwMCksIHRoZSBudW1iZXIgb2YgdmVydGljZXMgaW4gdGhlIGdyYXBoLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgZXhhY3RseSBOIHBvc2l0aXZlIGludGVnZXJzIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZSwgd2hlcmUgdGhlIG51bWJlciBhdCBwb3NpdGlvbiBpIGRlbm90ZXMgdGhlIGluZGV4IG9mIHRoZSBkZXN0aW5hdGlvbiBvZiB0aGUgb3V0Z29pbmcgZWRnZSBmcm9tIHZlcnRleCB3aXRoIGluZGV4IGkuIFRoZSB6ZXJvIHZhbHVlIHJlcHJlc2VudCB0aGF0IHRoZXJlIGlzIG5vIG91dGdvaW5nIGVkZ2UgZnJvbSB0aGUgdmVydGV4IHdpdGggaW5kZXggaS48XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBsaW5lIGNvbnRhaW5zIGEgc2luZ2xlIHBvc2l0aXZlIGludGVnZXIgUSAoMSAmbGU7IFEgJmxlOyAzMDAgMDAwKSwgdGhlIG51bWJlciBvZiBxdWVyaWVzLjxcL3A+XHJcblxyXG48cD5UaGUgcmVtYWluaW5nIFEgbGluZXMgY29udGFpbiBxdWVyaWVzIGluIHRoZSBmb3JtYXQgZGVzY3JpYmVkIGFib3ZlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHF1ZXJ5IG9mIHR5cGUgMSwgb3V0cHV0IHRoZSBpbmRleCBvZiB0aGUgdmVydGV4IHdoZXJlIHRoZSBtYXJibGUgc3RvcHMsIG9uZSBwZXIgbGluZSwgaW4gdGhlIG9yZGVyIG9mIHRoZSBleGVjdXRpb24gb2YgcXVlcmllcy4gSWYgdGhlIG1hcmJsZSBuZXZlciBzdG9wcywgb3V0cHV0IENJS0xVUyBpbnN0ZWFkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==