给你一个无向加权连通图,其中有 $$$n$$$ 个顶点和 $$$m$$$ 个边,没有循环和多条边。
第 $$$i$$$ 条边是 $$$e_i = (u_i, v_i, w_i)$$$;沿边 $$$e_i$$$ 的顶点 $$$u_i$$$ 和 $$$v_i$$$ 之间的距离为 $$$w_i$$$ ($$$1 \le w_i$$$)。该图是连通的,i。 e.对于任何一对顶点,它们之间至少存在一条仅由给定图的边组成的路径。
正权重情况下的最小生成树 (MST) 是连接的加权无向图的边的子集,该图将所有顶点连接在一起,并且在所有此类子集中具有最小的总成本(总成本是所选边的成本之和)。
您可以修改给定的图表。您可以执行的唯一操作如下:将某些边的权重增加$$$1$$$。您可以将每条边的权重增加数倍(可能是零)。
假设初始 MST 成本为 $$$k$$$。你的问题是用尽可能少的操作数增加一些边的权重,使得获得的图中 MST 的成本保持为 $$$k$$$,但 MST 是唯一的(这意味着在获得的图中只有一种方法可以选择 MST)。
您的问题是计算执行此操作所需的最少操作数。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5, n - 1 \le m \le 2 \cdot 10^5$$$) — 初始图中的顶点数和边数。
接下来的 $$$m$$$ 行每行包含三个整数。第 $$$i$$$ 行包含第 $$$i$$$ 边 $$$e_i$$$ 的描述。它由三个整数 $$$u_i、v_i$$$ 和 $$$w_i$$$ 表示($$$1 \le u_i, v_i \le n, u_i \ne v_i, 1 \le w \le 10^9$$$),其中 $$$u_i$$$ 和 $$$v_i$$$ 是由第 $$$i$$$ 条边连接的顶点, $$$w_i$$$ 是这条边的权重。
保证给定的图不包含循环和多条边(即,对于从 $$$1$$$ 到 $$$m$$$ $$$u_i \ne v_i$$$ 的每个 $$$i$$$ ,并且对于每个无序的顶点对 $$$(u, v)$$$ ,最多有一条边连接这对顶点)。还保证给定的图是连通的。
输出
打印一个整数 — 在不改变 MST 成本的情况下统一初始图的 MST 的最少操作数。
示例
输入 #1
8 10 1 2 1 2 3 2 2 4 5 1 4 2 6 3 3 6 1 3 3 5 2 3 7 1 4 8 1 6 2 4
输出 #1
1
输入 #2
4 3 2 1 3 4 3 4 2 4 1
输出 #2
0
输入 #3
3 3 1 2 1 2 3 2 1 3 3
输出 #3
0
输入#4
3 3 1 2 1 2 3 3 1 3 3
输出#4
1
输入 #5
1 0
输出 #5
0
输入 #6
5 6 1 2 2 2 3 1 4 5 3 2 4 2 1 4 2 1 5 3
输出 #6
2
注意
第一个例子对应的图片:
例如,您可以将边 $$$(1, 6)$$$ 或 $$$(6, 3)$$$ 的权重增加 $$$1$$$ 以统一 MST。
最后一个例子对应的图片:
例如,您可以将边 $$$(1, 5)$$$ 和 $$$(2, 4)$$$ 的权重增加 $$$1$$$ 以统一 MST。