题目描述

译自 JOISC 2015 Day2 T3「Road Development」。

有一个 $N$ 个点的无向图，一开始不存在任何边。给出 $Q$ 个操作：

• $1\ A_i\ B_i$：如果 $A_i$ 和 $B_i$ 不连通，加入一条白色边。如果 $A_i$ 和 $B_i$ 连通，把在 $A_i$ 到 $B_i$ 的最短路上的白边都染黑。
• $2\ A_i\ B_i$：求出如果执行上述操作后，有多少条边被染黑了。

输入格式

第一行包含两个整数 $N$ 和 $Q$，含义如题面所述。

接下来 $Q$ 行，第 $i$ 行包含三个整数 $T_i$，$A_i$ 和 $B_i$，表示一个操作，含义如题面所述。

输出格式

对于每个 $T_i = 2$ 的操作，如果 $A_i$ 和 $B_i$ 不连通，输出 $-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
0
1

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
1
1

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

0
1
0
-1

数据范围与提示

对于全部数据，满足 $ 2 \le N \le 10^5, 1 \le Q \le 3 \times 10^5, 1 \le T_i \le 2, 1 \le A_i, B_i \le N, A_i \ne B_i $。

本题共有 $5$ 个子任务。每个子任务的分数和附加限制如下：