시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 84 11 7 36.842%

문제

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

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

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

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

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

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

입력

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

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

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

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

출력

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

예제 입력

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

예제 출력

CIKLUS
CIKLUS
1
1
2

힌트