Äventyr 2

"Äventyr bortom tidpunkten, Sista Fiolen."

여러 시간축을 오가며 잊혀진 나라의 전설의 바이올린을 찾으려 한다. 시간축은 트리의 정점으로 나타내고, 트리의 간선은 두 시간축 사이를 오갈 수 있다는 뜻이다. 시간축에는 편의상 $1$부터 $N$까지 번호를 붙인다. 시간축 중 몇몇은 전설의 바이올린이 있는 시간축이고, 나머지는 아니다. 처음에는 바이올린이 있는 시간축이 하나도 없다. 트리가 주어진 뒤 다음 두 종류의 쿼리를 $Q$번 수행하라.

• 1 u: $u$번 시간축이 바이올린이 있는 시간축이 된다.
• 2 u: $u$번 시간축에서 출발해 바이올린이 있는 시간축에 도착할 때까지 간선을 최소 몇 번 지나야 하는지 출력한다. 바이올린이 있는 시간축이 하나도 없으면 $-1$을 출력한다.

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

둘째 줄에 $N-1$개의 정수 $A_2, A_3, \ldots, A_N$이 주어진다. $A_i$는 트리에서 $i$번 시간축의 부모가 $A_i$번 시간축이라는 뜻이다. ($1 \le A_i \le N$, $A_i \ne i$) 주어진 간선은 항상 하나의 트리를 이룬다. $N = 1$이면 둘째 줄은 비어 있다.

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

2번 쿼리마다 그 결과를 한 줄에 하나씩 순서대로 출력한다.