시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 97 21 17 26.984%

문제

"Äventyr bortom tidpunkten, Sista Fiolen."

여러 시간축을 이동하여 잊혀진 나라의 전설의 바이올린을 찾으려 한다. 시간축은 트리 상에서의 정점으로 표현할 수 있으며, 트리 상에서의 간선은 두 시간축 사이를 오갈 수 있음을 뜻한다. 각각의 시간축은 편의상 1부터 N까지의 자연수로 표현하자. 시간축 중 몇몇 시간축은 전설의 바이올린이 존재했던 시간축이고, 나머지는 아니다. 트리가 주어진 후, 다음과 같은 쿼리들을 Q번 수행하여라.

  • 1 u : u번 시간축이 바이올린이 있던 시간축이 된다.
  • 2 u : u번 시간축에서 시작하는 여행이 전설의 바이올린을 찾을 때까지 최소로 이동해야 하는 횟수를 출력한다. 방법이 없으면 -1을 출력한다.

입력

첫 줄에 N과 Q가 입력된다. (1 ≤ N, Q ≤ 105)

둘째 줄에 N-1개의 시간축 A가 주어지며, 이는 i번째 시간축의 트리 상 부모가 A번째 시간축임을 뜻한다. (i = 2, 3, ..., N, 1 ≤ AN, iA)

Q개의 줄 동안 쿼리들이 c v형식으로 주어진다. c = 1이면 1번 쿼리, c = 2이면 2번 쿼리를 수행한다. 1번 쿼리는 같은 시간축에 대해 2번 이상 반복되지 않는다.

출력

모든 2번 쿼리의 결과를 한 줄마다 출력한다.

예제 입력 1

20 10
1 2 3 3 5 5 2 8 9 9 8 1 13 14 14 1 17 18 18
2 10
1 14
2 6
2 19
1 20
2 4
2 17
2 1
2 2
2 12

예제 출력 1

-1
6
5
5
2
2
3
5

출처

Contest > 웰노운컵 > 제1회 웰노운컵 C2번