#214528. [JOISC 2015] 道路建设 / Road Development

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

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

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

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

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

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

题目

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

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

• 第一行包含两个整数 ，以空格分隔。表示 IOI 国有 个城市，JOI 教授关注了从建国起 年间的交通改善计划。
• 接下来的 行，第 行（）包含三个整数 ，以空格分隔。整数 表示在建国 年后制定的改善计划的实施状态：当 时表示该计划已实施，当 时表示该计划未实施而被放弃。整数 表示在建国 年后，制定了改善城市 与城市 之间交通状况的计划。

在标准输出上，对每个未实施而被放弃的改善计划，输出一行，表示若该计划被实施，则将铺设的道路数量。但若实施该计划会导致新建一条道路，则输出 。

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

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

数据范围

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

• （）
• （）
• （）
• （）

子任务

子任务 1 [10 分]

满足以下条件：

子任务 2 [25 分]

• 存在整数 （），满足 （）且 （）。

子任务 3 [25 分]

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

子任务 4 [25 分]

• 满足 的 （）的数量不超过 200。

子任务 5 [15 分]

无额外限制。

翻译由 Qwen3-235B 完成