LibreOJ

3000 「JOISC 2015 Day2」Road Development

内存限制：256 MB 时间限制：2000 ms

题目描述

译自 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

样例 2

样例 3

数据范围与提示

对于全部数据，满足 $ 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 $ 条边 25
4 满足 $ T_i = 2$ 的 $ i $ ($1 \le i \le Q$) 不超过 $ 200 $ 个 25
5 无附加限制 15

样例

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