Äventyr 1

"Äventyr bortom tidpunkten, Sista Fiolen."

여러 시간축을 오가며 잊힌 나라의 전설의 바이올린을 찾으려 한다. 시간축은 트리의 정점이고, 트리의 간선은 두 시간축 사이를 오갈 수 있다는 뜻이다. 시간축에는 1부터 $N$까지 번호가 붙어 있다. 시간축 중 몇몇은 전설의 바이올린이 존재했던 시간축이고, 나머지는 아니다. 처음에는 바이올린이 존재했던 시간축이 하나도 없다.

트리가 주어진 뒤 다음 두 종류의 쿼리를 $Q$번 수행한다.

• 1 u: $u$번 시간축이 바이올린이 존재했던 시간축이 된다.
• 2 u: $u$번 시간축에서 출발하는 여행이 바이올린이 존재했던 시간축에 도착할 때까지 간선을 최소 몇 번 지나야 하는지 출력한다. $u$번 시간축 자체가 바이올린이 존재했던 시간축이면 답은 0이다. 바이올린이 존재했던 시간축이 아직 하나도 없으면 -1을 출력한다.

첫째 줄에 $N$과 $Q$가 주어진다. ($1 \le N, Q \le 10^5$)

둘째 줄에 $N - 1$개의 정수 $A_2, A_3, \ldots, A_N$이 주어진다. $A_i$는 $i$번 시간축의 트리 상 부모이다. ($1 \le A_i \le N$, $A_i \ne i$) 이 문제에서 트리는 항상 한 줄로 이어진 경로이며 모든 $i$에 대해 $A_i = i - 1$이다. 즉 2번 정점의 부모는 1번, 3번 정점의 부모는 2번, ..., $N$번 정점의 부모는 $N - 1$번이다. $N = 1$이면 둘째 줄은 빈 줄이다.

다음 $Q$개의 줄에 쿼리가 c u 형식으로 한 줄에 하나씩 주어진다. $c = 1$이면 1번 쿼리, $c = 2$이면 2번 쿼리를 수행한다. ($c \in \{1, 2\}$, $1 \le u \le N$) 1번 쿼리는 같은 시간축에 대해 두 번 이상 주어지지 않는다.

모든 2번 쿼리의 답을 주어진 순서대로 한 줄에 하나씩 출력한다.