006 - 木

問題

木が与えられる．
木のノードには明かりがついていて最初はすべての明かりは消えている．

以下のクエリを処理しろ．

0. ノード u, v 間のパス中のノードすべての明かりをつける
1. ノード u, v 間のパス中のノードすべての明かりを消す
2. ノード u, v 間のパス中，明かりがついている区間で最も長いパスの長さを求める

入力

N Q
p0
:
pN-2
k0 u0 v0
:
kQ-1 uQ-1 vQ-1

1 行に木の頂点数 N とクエリの数 Q が与えられる．
2 行目から N-1 行にわたり，i 行目(1 ≦ i ≦ N)に，ノード i の親が与えられる．
N-1 行目から Q 行にわたり，クエリの種類 k，頂点 u, v が与えられる．
クエリの種類は問題文のクエリと対応している．

制約

1 ≦ N, Q ≦ 10⁵

与えられる木は連結していて，入力はそのたもろもろを満たす．

出力

2 のクエリごとに出力しろ

入出力

入力例1

10 10
7
9
7
0
7
4
0
7
0
2 1 1
1 5 9
0 9 6
2 1 9
1 5 1
2 1 2
0 6 7
0 8 3
1 9 9
2 1 1

出力

0
1
2
1

木

入力例2

10 10
5
1
1
5
0
5
5
1
1
1 4 3
1 5 0
1 9 5
0 6 4
0 4 1
0 2 0
1 0 5
0 4 6
2 1 9
2 3 0

出力

1
1

木

入力例3

10 7
0
1
7
6
7
0
0
6
6
0 0 1
2 6 3
1 3 0
1 5 6
1 8 6
1 9 0
2 9 3

出力

0
5

木

入力例4

10 7
0
4
2
0
1
9
1
9
4
2 4 2
0 9 0
1 0 4
1 1 6
1 8 4
2 0 8
2 7 0

出力

0
4
2

木

入力例5

10 6
0
9
5
1
0
3
9
4
5
0 0 9
0 1 3
1 7 1
1 8 8
0 9 6
2 6 8

出力

2

木

最終的な木 6->8 の中では 0, 1 の連続した区間が最も長い．