COCI 2010/2011 contest#7- 마블 게임(KUGLICE) > 문제은행 : 정보올림피아드&알고리즘




2445 : 마블 게임(KUGLICE)

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
8 회   
시도횟수
33 회   

문제

근우와 범수는 마블게임을 좋아한다. 재미있는 마블게임을 연구하던 근우는 범수에게 알려주고 싶은 마블게임을 생각해냈다.

이 게임에서는 기껏해야 하나의 간선을 갖는 방향그래프를 이용한다. 그리고 여러 개의 정점 중에 한 곳에 마블을 놓는다. 마블이 어떤 정점 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 를 출력한다.


입력 예

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

출력 예

CIKLUS
CIKLUS
1
1
2

Hint!

입력 예 2
5
0 3 5 3 4
6
1 1
1 2
2 4
1 2
2 3
1 2

출력 예 2
1
CIKLUS
4
3




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP