AT_joisc2015_g.道路整備

JOISC2015 Day2T3 道路整备

给定一个$N$个点的森林，初始森林上没有边。接下来进行$Q$次操作，操作有以下两种：

$1\ u\ v$：如果当前$u\ v$不连通，则在森林上添加一条边$(u,v)$，边权为$1$；否则将森林中路径$(u,v)$上的所有边的边权赋为$0$。

$2\ u\ v$：询问此时森林上$(u,v)$对应的路径的边权和。

第一行两个正整数$N,Q$，

接下来$Q$行每行三个正整数$type,u,v$描述一个操作。

对于每个$2$操作输出一行表示路径边权和，如果森林上$(u,v)$不连通输出-1。

$1 \leq N \leq 10^5$

$1 \leq Q \leq 3 \times 10^5$

$type \in \{1,2\} , 1 \leq u,v \leq N , u \neq v$

样例

样例输入1

3 7
1 1 2
2 2 1
2 2 3
1 2 1
2 1 2
1 2 3
2 1 3

样例输出1

1
-1
0
1

样例输入2

6 8
1 1 3
1 6 1
1 2 5
2 3 6
1 3 6
1 4 1
2 4 3
2 2 5

样例输出2

2
1
1

样例输入3

7 11
1 5 1
1 6 2
1 1 3
1 3 5
1 5 7
1 4 5
1 4 1
2 1 3
2 3 7
2 4 3
2 5 6

样例输出3

0
1
0
-1