题目描述

IOI 国由 $N$ 个城市组成，这些城市编号为 $1, 2, \dots, N$。JOI 教授对 IOI 国道路网络建设的过程产生了兴趣。

JOI 教授查阅了有关 IOI 国历史的资料，发现以下事实：

• IOI 国的城市自建国以来至今保持不变。IOI 国建国初期没有任何连接城市的道路。
• 在 IOI 国建国 $i$ 年后（$1 \le i \le Q$），制定了改善城市 $A_i$ 与城市 $B_i$ 之间交通状况的计划。
• 制定的改善计划中，部分计划得以实施，而部分计划则未实施而被放弃。
• 哪些计划被实施，哪些被放弃，从资料中可以明确得知。
• 所有被实施的改善计划均在一年内完成。

此外，从其他文献中得知，城市 $A_i$ 与城市 $B_i$ 之间交通状况的改善计划具有以下特点：

• 若在计划制定时，无法通过已建成的道路从城市 $A_i$ 移动到城市 $B_i$，则新建一条连接城市 $A_i$ 与城市 $B_i$ 的双向道路。新建的道路为未铺设路面的道路。
• 若在计划制定时，可以通过已建成的道路从城市 $A_i$ 移动到城市 $B_i$，则在所有可能的路径中，选择使用道路数量最少的路径，并将该路径中包含的所有未铺设路面的道路铺设路面。若存在多条使用道路数量最少的路径，则对所有这些路径中的未铺设路面道路进行统一铺设。已铺设路面的道路不会再次铺设。

JOI 教授为进一步调查，针对那些未实施而被放弃的改善计划，计算若仅这些计划被追加实施，每个计划中将铺设多少条道路。

题目

给定 IOI 国交通状况的改善计划及其实施情况，编写一个程序，对每个未实施而被放弃的改善计划，计算若该计划被实施，则将铺设多少条道路。

输入格式

从标准输入读入以下数据：

• 第一行包含两个整数 $N, Q$，以空格分隔。表示 IOI 国有 $N$ 个城市，JOI 教授关注了从建国起 $Q$ 年间的交通改善计划。
• 接下来的 $Q$ 行，第 $i$ 行（$1 \le i \le Q$）包含三个整数 $T_i, A_i, B_i$，以空格分隔。整数 $T_i$ 表示在建国 $i$ 年后制定的改善计划的实施状态：当 $T_i = 1$ 时表示该计划已实施，当 $T_i = 2$ 时表示该计划未实施而被放弃。整数 $A_i, B_i$ 表示在建国 $i$ 年后，制定了改善城市 $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

提示

样例 1 解释

在该输入示例中，IOI 国的交通改善计划执行情况如下：

• IOI 国有 3 个城市，建国初期没有任何连接这些城市的道路。
• 建国 1 年后，实施了城市 1 与城市 2 之间交通状况的改善计划。此时无法通过已建成的道路从城市 1 移动到城市 2，因此该计划导致新建了一条连接这两个城市的道路。
• 建国 2 年后，制定了城市 2 与城市 1 之间交通状况的改善计划，但未实施而被放弃。此时可以通过 1 条已建成的道路从城市 2 移动到城市 1，且该道路尚未铺设路面，因此对该改善计划对应的输出为 1。
• 建国 3 年后，制定了城市 2 与城市 3 之间交通状况的改善计划，但未实施而被放弃。此时无法通过已建成的道路从城市 2 移动到城市 3，因此对该改善计划对应的输出为 -1。
• 建国 4 年后，实施了城市 2 与城市 1 之间交通状况的改善计划。此时可以通过已建成的道路从城市 2 移动到城市 1，因此该计划导致将连接这两个城市的道路铺设路面。
• 建国 5 年后，制定了城市 1 与城市 2 之间交通状况的改善计划，但未实施而被放弃。此时可以通过 1 条已建成的道路从城市 1 移动到城市 2，且该道路已铺设路面，因此对该改善计划对应的输出为 0。
• 建国 6 年后，实施了城市 2 与城市 3 之间交通状况的改善计划。此时无法通过已建成的道路从城市 2 移动到城市 3，因此该计划导致新建了一条连接这两个城市的道路。
• 建国 7 年后，制定了城市 1 与城市 3 之间交通状况的改善计划，但未实施而被放弃。此时可以通过 2 条已建成的道路从城市 1 移动到城市 3，其中仅 1 条道路未铺设路面，因此对该改善计划对应的输出为 1。

数据范围

所有输入数据满足以下条件：

• $2 \le N \le 100000$
• $1 \le Q \le 300000$
• $1 \le T_i \le 2$（$1 \le i \le Q$）
• $1 \le A_i \le N$（$1 \le i \le Q$）
• $1 \le B_i \le N$（$1 \le i \le Q$）
• $A_i \ne B_i$（$1 \le i \le Q$）

子任务

子任务 1 [10 分]

满足以下条件：

• $N \le 1000$
• $Q \le 3000$

子任务 2 [25 分]

• 存在整数 $P$（$1 \le P \le Q-1$），满足 $T_i = 1$（$1 \le i \le P$）且 $T_i = 2$（$P+1 \le i \le Q$）。

子任务 3 [25 分]

• 对所有满足 $T_i = 1$ 的 $i$（$1 \le i \le Q$），以下任一条件成立：
  • 在实施建国 $i$ 年后的改善计划之前，无法通过已建成的道路从城市 $A_i$ 移动到城市 $B_i$。
  • 在实施建国 $i$ 年后的改善计划之前，可以通过已建成的道路中不超过 200 条道路从城市 $A_i$ 移动到城市 $B_i$。

子任务 4 [25 分]

• 满足 $T_i = 2$ 的 $i$（$1 \le i \le Q$）的数量不超过 200。

子任务 5 [15 分]

无额外限制。

翻译由 Qwen3-235B 完成