문제
근우와 범수는 마블게임을 좋아한다. 재미있는 마블게임을 연구하던 근우는 범수에게 알려주고 싶은 마블게임을 생각해냈다.
이 게임에서는 기껏해야 하나의 간선을 갖는 방향그래프를 이용한다. 그리고 여러 개의 정점 중에 한 곳에 마블을 놓는다. 마블이 어떤 정점 X에 있을 때 그 마블은 인접해 있는 노드가 하나의 간선으로 연결되어 있다면 인접한 노드로 움직인다. 마블은 진출간선이 없는 노드를 만날 때까지 움직이고 진출간선이 없는 노드에서 멈춘다.
범수는 이 게임을 좀 더 명확히 이해하기 위해 근우에게 몇 개의 연속된 질의를 던진다. 그 질의의 종류는 다음 두 가지이다.
- 1 X - “현재 그래프의 X정점에 마블을 놓을 경우 어느 노드에서 마블이 멈추게 되는가? ”에 대한 답을 출력해야 한다. (질의타 입은 1 노드번호는 X 인 경우)
- 2 X - X의 진출간선을 제거한다. X 노드는 진출간선이 반드시 존재한다. (질의타입은 2 노드번호는 X 인 경우)
이러한 질의가 연속되어 있을 경우 질의의 실행은 순서대로 이루어져야 하며 이 전 질의를 실행한 결과에 이어서 반영된다.
입력
첫 행에 그래프의 노드수를 나타내는 양의 정수 N(1≤N≤300,000)이 주어진다.
다음 행에는 공백으로 구분하여 N 개의 양의 정수가 주어지는데 해당 인덱스 노드로부터 주어진 수로의 진출간선을 의미한다. 예를 들어 2 3 0 이 주어졌다면 1번 노드는 2번 노드로의 간선이 존재하고, 2번 노드는 3번으로, 그리고 3번 노드는 진출 간선이 없음을 의미한다.
다음 행에는 질의의 수를 나타내는 양의 정수 Q(1≤Q≤300,000)가 입력된다.
이 후 Q 개의 라인에 걸쳐 위에서 제시한 포맷 형태의 질의가 입력된다.
출력
질의 타입이 1인 경우 마블이 멈추게 되는 노드의 인덱스번호를 하나의 라인에 출력한다. 마블이 멈추지 않는 다면 CIKLUS 를 출력한다.
예제1
입력
3
131
7
11
12
21
12
11
22
12
출력
CIKLUS
CIKLUS
1
1
2
힌트
출처
COCI 2010/2011 contest#7