Informatica Online Judge

  TNCKS are GAY [0672 / 02A0]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 22   Total Tried : 32


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

바람 잘 날 없는 더블릿 나라에는 tnck라는 종족 N명이 옹기종기 모여서 살고 있습니다.
그들에게는 각각 1번부터 N번까지의 고유한 번호가 있습니다.

이 종족은 어떻게 하다 보니(?) XX염색체에 문제가 생겨 여자가 모두 사라졌습니다. ㅜ.ㅜ 남자인 그들은 원래 여자를 좋아했어야 하지만, 좋아할 여자가 없었고, 애정 결핍에 빠진 그들은 남자라도 좋아해야만 했습니다. 그들은 일부일처제를 유지했기 때문에 아무도 좋아하지 않거나, 자신을 좋아하거나, 다른 한 사람을 좋아합니다.

쓸데없는 일에 관심이 많은 GENIUS ainta는 이 사실을 알고 당신에게 tnck 종족에서 임의의 한 tnck을 뽑아, 그가 좋아하는 tnck의 좋아하는 tnck의, …, 이렇게 계속 반복하여 최종적으로 도달하는 tnck의 번호를 알려 달라고 합니다. (죽었을 경우에도 번호는 유지됩니다.) 당신은 귀찮은 관계로 프로그램을 제작해서 그것을 주기로 합니다.

당신은 tnck 종족과 친하기 때문에 어느 tnck가 누구를 좋아하는지를 모두 알고 있고, 어떤 tnck가 죽었는지에 대한 소식을 실시간으로 접할 수 있습니다. (tnck들은 수명이 작아 빨리 죽습니다.) tnck들은 당신과 GENIUS ainta가 친하다는 것을 알고 있기 때문에 GENIUS ainta에게도 소식을 전해 줍니다.

자, 이제 우리는 GENIUS ainta의 명령을 들어주는 프로그램을 작성해야만 합니다.
GENIUS ainta는 우리에게 tnck 종족의 개체 수 N(1N300,000)과 명령의 수와 죽었다는 소식의 수의 합 Q(1Q300,000)를 본인이 일일이 타이핑해서(?) 우리에게 알려줍니다.

Q개의 소식 또는 명령은 아래와 같이 구성됩니다.

•“1 X” : X번 tnck가 좋아하는 tnck의 좋아하는 tnck의, …, 이렇게 계속 반복하여 최종적으로 도달하는 tnck의 번호를 출력해야 합니다. 이 때 회로를 이룬다면 “CYCLE”을 출력합니다. (만약, 반복하여 도달한 어떤 tnck가 자신을 좋아한다면, 그 역시 회로입니다.) 당연하지만 한 번 죽은 tnck는 한 번 더 죽을 수는 없습니다.

•“2 X” : X번 tnck가 죽었다는 소식을 나타냅니다. tnck 종족은 한 번 사랑이 영원한 사랑이기 때문에, X번 tnck를 좋아했던 tnck들은 죽은 후에도 X번 tnck를 좋아하지만, X번 tnck는 죽었기 때문에 하늘에서 아무도 좋아하지 않게 됩니다. (ㅠㅠ)

점수를 얻고 싶다면 쓸 데 없는 남의 일에 관심이 많은 GENIUS ainta를 위해 프로그램을 만들어 주세요. :)

Input

첫째 줄에 tnck들의 수 N이 주어집니다.
둘째 줄에 1번부터 N번까지 tnck들이 각각 몇 번 tnck를 좋아하는지에 대한 정보가 공백을 사이로 두고 주어집니다. 만약 k번 tnck가 죽었다면 그 번호에 대해 0이 입력됩니다.
셋째 줄에 명령과 소식의 수의 합 Q가 주어집니다.
그 다음 Q개의 줄에 “1 X” 또는 “2 X”가 주어집니다. (1<=X<=N)

Output

“1 X”가 입력되면 입력 순서대로 GENIUS ainta를 위해 한 줄에 하나씩 물음에 대한 답을 출력합니다.

IO Example

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

출력
1
CYCLE
4
3

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]