問題
木が与えられる．
木のノードには明かりがついていて最初はすべての明かりは消えている．
以下のクエリを処理しろ．
- ノード u, v 間のパス中のノードすべての明かりをつける
- ノード u, v 間のパス中のノードすべての明かりを消す
- ノード 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 ≦ 105
与えられる木は連結していて，入力はそのたもろもろを満たす．
出力
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 の連続した区間が最も長い．