#3000. 「JOISC 2015 Day2」Road Development

---

题目描述

译自 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$，否则输出染黑的白边数目。

---

样例 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

---

样例 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
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

输出

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$ 个子任务。每个子任务的分数和附加限制如下：

Subtask	附加限制	分数
1	$N \le 1000$，$Q \le 3000$	$10$
2	存在一个 $P$ $(1 \le P \le Q - 1)$，对于 $T_i = 1$ 的 $i$ 有 $1 \le i \le P$，对于 $T_i = 2$ 的 $i$ 有 $P + 1 \le i \le Q$	$25$
3	对于 $T_i=1$ 的 $i$，要么 $A_i$ 和 $B_i$ 不连通，要么 $A_i$ 和 $B_i$ 所在的连通块有不超过 $200$ 条边
4	满足 $T_i = 2$ 的 $i$ $(1 \le i \le Q)$ 不超过 $200$ 个
5	无附加限制	$15$