시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 1234 | 356 | 251 | 30.535% |
민혁이는 매주 금요일마다 지수와 함께 논다. 이번 주 금요일은 지수와 민혁이가 친구가 된지 십 년이 되는 날이다. 따라서, 둘은 엄청난 게임을 하기로 결정했다. 민혁이는 바닥이 흙인 운동장을 예약했고, 지수는 조약돌 한 개를 들고 왔다.
먼저 민혁이는 운동장 바닥에 나뭇가지로 방향 그래프를 그린다. 이 그래프에서 모든 정점은 많아야 한 개의 나가는 간선(outgoing edge)를 가질 수 있다. 그 다음 민혁이는 조약돌을 한 정점 위에 올려 놓는다. 만약, 조약돌이 있는 정점에 나가는 간선이 있다면, 조약돌은 그 간선을 통해서 이동할 수 없을 때까지 계속해서 이동한다. 더 이상 이동할 수 있는 정점이 없다면, 조약돌은 그 자리에서 멈춘다. 조약돌은 그래프를 무한히 이동할 수도 있고, 방문하지 않는 정점이 있을 수도 있다.
민혁이는 지수가 게임의 규칙을 확실하게 이해했는지 알기 위해서 다음과 같은 두 가지 질문을 하려고 한다.
민혁이의 질문이 주어졌을 때, 지수의 답변을 출력하는 프로그램을 작성하시오.
첫째 줄에 그래프의 정점의 개수 N이 주어진다. (1 ≤ N ≤ 300,000)
둘째 줄에는 각 정점의 나가는 간선이 공백으로 구분되어서 주어진다. 정점의 번호는 1부터 시작하며, 나가는 간선이 없는 경우에는 0이 주어진다.
셋째 줄에는 민혁이의 질문의 수 Q가 주어진다. (1 ≤ Q ≤ 300,000)
넷째 줄부터 Q개 줄에는 문제 설명에 나온 질문 형식대로 민혁이의 질문이 주어진다.
1로 시작하는 쿼리가 주어질때 마다, 조약돌이 멈추는 정점의 번호를 한 줄에 하나씩 출력한다. 만약, 어떤 정점에 멈추지 않고 무한히 이동한다면, CIKLUS를 출력한다.
3 2 3 1 7 1 1 1 2 2 1 1 2 1 1 2 2 1 2
CIKLUS CIKLUS 1 1 2
5 0 3 5 3 4 6 1 1 1 2 2 4 1 2 2 3 1 2
1 CIKLUS 4 3