P14411 [JOISC 2015] 道路建设 / Road Development

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$。

### 样例 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 完成