#3000. 「JOISC 2015 Day2」Road Development

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Chiaki

题目描述

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

数据范围与提示

对于全部数据,满足 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