15564번 - Äventyr 2

"Äventyr bortom tidpunkten, Sista Fiolen."

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

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

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

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

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

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