You are given an undirected weighted connected graph with $n$ vertices and $m$ edges without loops and multiple edges.

The $i$-th edge is $e_i = (u_i, v_i, w_i)$; the distance between vertices $u_i$ and $v_i$ along the edge $e_i$ is $w_i$ ($1 \le w_i$). The graph is connected, i. e. for any pair of vertices, there is at least one path between them consisting only of edges of the given graph.

A minimum spanning tree (MST) in case of positive weights is a subset of the edges of a connected weighted undirected graph that connects all the vertices together and has minimum total cost among all such subsets (total cost is the sum of costs of chosen edges).

You can modify the given graph. The only operation you can perform is the following: increase the weight of some edge by $1$. You can increase the weight of each edge multiple (possibly, zero) times.

Suppose that the initial MST cost is $k$. Your problem is to increase weights of some edges with minimum possible number of operations in such a way that the cost of MST in the obtained graph remains $k$, but MST is unique (it means that there is only one way to choose MST in the obtained graph).

Your problem is to calculate the minimum number of operations required to do it.


-----Input-----

The first line of the input contains two integers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5, n - 1 \le m \le 2 \cdot 10^5$) — the number of vertices and the number of edges in the initial graph.

The next $m$ lines contain three integers each. The $i$-th line contains the description of the $i$-th edge $e_i$. It is denoted by three integers $u_i, v_i$ and $w_i$ ($1 \le u_i, v_i \le n, u_i \ne v_i, 1 \le w \le 10^9$), where $u_i$ and $v_i$ are vertices connected by the $i$-th edge and $w_i$ is the weight of this edge.

It is guaranteed that the given graph doesn't contain loops and multiple edges (i.e. for each $i$ from $1$ to $m$ $u_i \ne v_i$ and for each unordered pair of vertices $(u, v)$ there is at most one edge connecting this pair of vertices). It is also guaranteed that the given graph is connected.


-----Output-----

Print one integer — the minimum number of operations to unify MST of the initial graph without changing the cost of MST.


-----Examples-----
Input
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

Output
1

Input
4 3
2 1 3
4 3 4
2 4 1

Output
0

Input
3 3
1 2 1
2 3 2
1 3 3

Output
0

Input
3 3
1 2 1
2 3 3
1 3 3

Output
1

Input
1 0

Output
0

Input
5 6
1 2 2
2 3 1
4 5 3
2 4 2
1 4 2
1 5 3

Output
2



-----Note-----

The picture corresponding to the first example: [Image]

You can, for example, increase weight of the edge $(1, 6)$ or $(6, 3)$ by $1$ to unify MST.

The picture corresponding to the last example: $\$ 8$

You can, for example, increase weights of edges $(1, 5)$ and $(2, 4)$ by $1$ to unify MST.

Source: codeforces | Difficulty: HARD
Tags: Spanning trees

Sorting

Graph algorithms

Greedy algorithms


Solutions:
(n, m) = map(int, input().split())
l = []
for i in range(m):
	(a, b, c) = map(int, input().split())
	l.append((c, a, b))
l.sort()
f = [i for i in range(n + 1)]

def r(a):
	if a == f[a]:
		return a
	f[a] = r(f[a])
	return f[a]
cnt = 0
i = 0
while i < m:
	j = i
	while j < m and l[j][0] == l[i][0]:
		j = j + 1
	num = 0
	for k in range(i, j):
		x = r(l[k][1])
		y = r(l[k][2])
		if x != y:
			num = num + 1
	for k in range(i, j):
		x = r(l[k][1])
		y = r(l[k][2])
		if x != y:
			f[y] = x
			num = num - 1
	cnt = cnt + num
	i = j
print(cnt)


import sys
input = lambda : sys.stdin.readline().strip()
ipnut = input

def find(a):
	st = []
	while a != dsu[a]:
		st.append(a)
		a = dsu[a]
	for j in st:
		dsu[j] = a
	return a

def union(a, b, f):
	a = find(a)
	b = find(b)
	if f:
		dsu[a] = b
	else:
		dsu[b] = a
(n, m) = map(int, input().split())
if m == 0:
	print(0)
	exit(0)
dsu = [i for i in range(n)]
h = []
for i in range(m):
	(a, b, c) = map(int, ipnut().split())
	h.append((c, a - 1, b - 1))
h.sort()
lc = 0
ans = 0
heh = [[h[0]]]
for i in h[1:]:
	if heh[-1][0][0] == i[0]:
		heh[-1].append(i)
	else:
		heh.append([i])
ab = []
for h in heh:
	lol = []
	for (c, a, b) in h:
		if find(a) != find(b):
			lol.append((a, b))
	for (a, b) in lol:
		if find(a) == find(b):
			ans += 1
		else:
			union(a, b, ans % 2)
print(ans)


class DisjoinSet:

	def __init__(self, n):
		self.n = n
		self.dad = [i for i in range(n + 1)]
		self.cant = [1] * (n + 1)

	def SetOf(self, n):
		if self.dad[n] == n:
			return n
		self.dad[n] = self.SetOf(self.dad[n])
		return self.dad[n]

	def Merge(self, a, b):
		(a, b) = (self.SetOf(a), self.SetOf(b))
		if a != b:
			if self.cant[b] > self.cant[a]:
				(a, b) = (b, a)
			self.cant[a] += self.cant[b]
			self.dad[b] = a
			return True
		return False

def Kruskal(l, n):
	l.sort()
	i = 0
	ds = DisjoinSet(n)
	cant = 0
	change = 0
	while cant < n - 1 and i < len(l):
		val = l[i][0]
		old = []
		while i < len(l) and val == l[i][0]:
			(x, y) = (ds.SetOf(l[i][1]), ds.SetOf(l[i][2]))
			if x != y:
				old.append((x, y))
			i += 1
		change += len(old)
		for (x, y) in old:
			change -= ds.Merge(x, y)
	return change
(n, m) = input().split()
(n, m) = (int(n), int(m))
e = []
for i in range(m):
	(x, y, c) = input().split()
	e.append((int(c), int(x), int(y)))
print(Kruskal(e, n))


(n, m) = list(map(int, input().split()))
e = [tuple(map(int, input().split())) for i in range(m)]
e = sorted(((w, u, v) for (u, v, w) in e))
(p, r) = ([i for i in range(n + 1)], [0] * (n + 1))

def find(x):
	if p[x] != x:
		p[x] = find(p[x])
	return p[x]

def union(x, y):
	(x, y) = (p[x], p[y])
	if r[x] < r[y]:
		p[x] = y
	else:
		p[y] = x
		if r[x] == r[y]:
			r[x] += 1
ans = 0
i = 0
while i < m:
	j = i + 1
	while j < m and e[j][0] == e[i][0]:
		j += 1
	tmp = [(u, v) for (w, u, v) in e[i:j] if find(u) != find(v)]
	for (u, v) in tmp:
		if find(u) == find(v):
			ans += 1
		else:
			union(u, v)
	i = j
print(ans)


class UnionFind(object):

	def __init__(self, n):
		self.root = [i for i in range(n)]
		self.size = [1 for i in range(n)]

	def find(self, x):
		if self.root[x] == x:
			return x
		self.root[x] = self.find(self.root[x])
		return self.root[x]

	def union(self, x, y):
		(x, y) = (self.find(x), self.find(y))
		if x == y:
			return False
		if self.size[x] < self.size[y]:
			(x, y) = (y, x)
		self.size[x] += self.size[y]
		self.root[y] = x
		return True

def main():
	(n, m) = map(int, input().split())
	edge_list = []
	for _ in range(m):
		edge_list.append(list(map(int, input().split())))
	union_find = UnionFind(n + 1)
	edge_list.sort(key=lambda x: x[2])
	p1 = ret = 0
	while p1 < m:
		p2 = p1
		while p2 < m and edge_list[p1][2] == edge_list[p2][2]:
			p2 += 1
		avail = used = 0
		for i in range(p1, p2):
			if union_find.find(edge_list[i][0]) != union_find.find(edge_list[i][1]):
				avail += 1
		for i in range(p1, p2):
			if union_find.union(edge_list[i][0], edge_list[i][1]):
				used += 1
		ret += avail - used
		p1 = p2
	print(ret)
main()


a = input().split()
(n, m) = (int(a[0]), int(a[1]))
f = [i for i in range(0, n + 1)]

class edge:

	def __init__(self, U, V, W):
		self.u = U
		self.v = V
		self.w = W
l = []
for i in range(m):
	a = input().split()
	(u, v, w) = (int(a[0]), int(a[1]), int(a[2]))
	l.append(edge(u, v, w))
l.sort(key=lambda x: x.w)

def r(a):
	if a != f[a]:
		f[a] = r(f[a])
	return f[a]
cnt = 0
i = 0
while i < m:
	j = i
	while l[i].w == l[j].w:
		j = j + 1
		if j == m:
			break
	num = 0
	for k in range(i, j):
		x = r(l[k].u)
		y = r(l[k].v)
		if x != y:
			num = num + 1
	for k in range(i, j):
		x = r(l[k].u)
		y = r(l[k].v)
		if x != y:
			f[y] = x
			num = num - 1
	cnt = cnt + num
	i = j
print(cnt)


[n, m] = map(int, input().rstrip().split(' '))
edges = []
ds = [i for i in range(n + 1)]
ans = 0

def head(x):
	if x == ds[x]:
		return x
	ds[x] = head(ds[x])
	return ds[x]

def union(x, y):
	X = head(x)
	Y = head(y)
	ds[max(X, Y)] = min(X, Y)
for i in range(m):
	[u, v, w] = map(int, input().rstrip().split(' '))
	edges.append((u, v, w))
edges.sort(key=lambda x: x[2])
i = 0
while i < m:
	s = {}
	cnt = 0
	w = edges[i][2]
	while i < m and edges[i][2] == w:
		u = head(edges[i][0])
		v = head(edges[i][1])
		i += 1
		if u == v:
			continue
		U = min(u, v)
		V = max(u, v)
		s[U, V] = s.get((U, V), 0) + 1
	for ((u, v), tot) in s.items():
		if head(u) != head(v):
			ans += tot - 1
			union(u, v)
		else:
			ans += tot
print(ans)


(n, m) = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(m)]
edge = sorted(edge, key=lambda x: x[2])

class Union:

	def __init__(self, n):
		self.p = [i for i in range(n + 1)]
		self.rank = [0] * (n + 1)

	def find(self, x):
		if self.p[x] != x:
			self.p[x] = self.find(self.p[x])
		return self.p[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			if self.rank[x] < self.rank[y]:
				self.p[x] = y
				self.rank[y] += self.rank[x]
			else:
				self.p[y] = x
				self.rank[x] += self.rank[y]
cnt = 0
used = [0] * m
(l, r) = (0, 1)
U = Union(n)
while l < m:
	try:
		while r < m and edge[r][2] == edge[l][2]:
			r += 1
	except:
		print('bl1')
	try:
		for i in range(l, r):
			(u, v, w) = edge[i]
			if U.find(u) == U.find(v):
				used[i] = 1
	except:
		print('bl2')
	try:
		for i in range(l, r):
			if used[i] == 1:
				continue
			(u, v, w) = edge[i]
			if U.find(u) == U.find(v):
				cnt += 1
			else:
				U.union(u, v)
	except:
		print('bl3')
		print(u, v)
		print(U.find(u))
		print(U.find(v))
	l = r
	r = l + 1
print(cnt)


import sys
input = sys.stdin.readline

def find(x, par):
	while x != par[x]:
		x = par[x]
	return x
(n, m) = map(int, input().split())
A = []
for i in range(m):
	A.append(list(map(int, input().split())))
A.sort(key=lambda x: x[2])
par = [i for i in range(n + 1)]
i = 0
ans = 0
while i < m:
	j = i
	C = {}
	if find(A[j][1], par) == find(A[j][0], par):
		C[j] = 1
	else:
		C[j] = 0
	j = j + 1
	while j < m:
		if A[j][2] == A[j - 1][2]:
			if find(A[j][1], par) == find(A[j][0], par):
				C[j] = 1
			else:
				C[j] = 0
			j = j + 1
		else:
			break
	for k in range(i, j):
		if C[k] == 0:
			(a, b) = (find(A[k][0], par), find(A[k][1], par))
			if a != b:
				(par[a], par[b]) = (min(a, b), min(a, b))
			else:
				ans = ans + 1
	i = j
print(ans)


import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(n, m) = I()
ed = [I() for i in range(m)]
ed.sort(key=lambda x: x[2])
p = [i for i in range(n)]

def find(x):
	while x != p[x]:
		x = p[x]
	return x

def union(a, b):
	x = find(a)
	y = find(b)
	if x != y:
		p[y] = p[x] = min(x, y)
		return 1
	return 0
an = 0
ce = 0
pos = [1] * m
i = 0
while ce < n - 1:
	(x, y, w) = ed[i]
	for j in range(i, m):
		if ed[j][2] != w:
			break
		(a, b, c) = ed[j]
		if find(a - 1) == find(b - 1):
			pos[j] = 0
	for j in range(i, m):
		(x, y, b) = ed[j]
		if ed[j][2] != w:
			break
		if pos[j]:
			d = union(x - 1, y - 1)
			if d == 0:
				an += 1
			else:
				ce += 1
	if ce == n - 1:
		break
	i = j
print(an)


import sys

def get(v):
	if v == prev[v]:
		return v
	prev[v] = get(prev[v])
	return prev[v]

def join(u, v):
	u = get(u)
	v = get(v)
	if u != v:
		if size[u] < size[v]:
			(u, v) = (v, u)
		prev[v] = u
		size[u] += size[v]
(n, m) = map(int, sys.stdin.readline().split())
edges = [0] * m
for i in range(m):
	(u, v, w) = map(int, sys.stdin.readline().split())
	edges[i] = (u - 1, v - 1, w)
edges.sort(key=lambda e: e[2])
prev = list(range(n))
size = [1] * n
res = 0
(l, r) = (0, 1)
while l < m:
	while r < m and edges[l][2] == edges[r][2]:
		r += 1
	res += r - l
	for i in range(l, r):
		if get(edges[i][0]) == get(edges[i][1]):
			res -= 1
	for i in range(l, r):
		if get(edges[i][0]) != get(edges[i][1]):
			join(edges[i][0], edges[i][1])
			res -= 1
	l = r
print(res)


import os, sys
from io import BytesIO, IOBase

def find(node, parent):
	if parent[node] != node:
		parent[node] = find(parent[node], parent)
	return parent[node]

def union(node1, node2, parent, rank):
	if rank[node1] < rank[node2]:
		(node1, node2) = (node2, node1)
	parent[node2] = node1
	if rank[node1] == rank[node2]:
		rank[node1] += 1
	return node1

def main():
	(n, m) = map(int, input().split())
	edges = [tuple(map(int, input().split())) for _ in range(m)]
	edges.sort(key=lambda edge: edge[2])
	previous_weight = -1
	operation = []
	parent = [i for i in range(n + 1)]
	rank = [0] * (n + 1)
	ans = 0
	for (u, v, weight) in edges:
		if weight == previous_weight:
			(node1, node2) = (find(u, parent), find(v, parent))
			if node1 != node2:
				operation.append((node1, node2))
		else:
			ans += len(operation)
			for (node1, node2) in operation:
				node1 = find(node1, parent)
				node2 = find(node2, parent)
				if node1 != node2:
					ans -= 1
					union(node1, node2, parent, rank)
			previous_weight = weight
			(node1, node2) = (find(u, parent), find(v, parent))
			if node1 != node2:
				operation = [(node1, node2)]
			else:
				operation.clear()
	ans += len(operation)
	for (node1, node2) in operation:
		node1 = find(node1, parent)
		node2 = find(node2, parent)
		if node1 != node2:
			ans -= 1
			union(node1, node2, parent, rank)
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


class UnionFind:

	def __init__(self, n):
		self.par = [-1] * n
		self.rank = [0] * n

	def Find(self, x):
		if self.par[x] < 0:
			return x
		else:
			self.par[x] = self.Find(self.par[x])
			return self.par[x]

	def Unite(self, x, y):
		x = self.Find(x)
		y = self.Find(y)
		if x != y:
			if self.rank[x] < self.rank[y]:
				self.par[y] += self.par[x]
				self.par[x] = y
			else:
				self.par[x] += self.par[y]
				self.par[y] = x
				if self.rank[x] == self.rank[y]:
					self.rank[x] += 1

	def Same(self, x, y):
		return self.Find(x) == self.Find(y)

	def Size(self, x):
		return -self.par[self.Find(x)]

class LCA:

	def __init__(self, g, root, f=max, ide_ele=0):
		self.n = len(g)
		self.root = root
		self.f = f
		self.ide_ele = ide_ele
		self.num = self.n.bit_length()
		self.depth = [0] * self.n
		self.parent = [[-1] * self.n for i in range(self.num)]
		self.path = [[self.ide_ele] * self.n for i in range(self.num)]
		s = [root]
		while s:
			v = s.pop()
			for (c, u) in g[v]:
				if u == self.parent[0][v]:
					continue
				self.parent[0][u] = v
				self.path[0][u] = c
				self.depth[u] = self.depth[v] + 1
				s.append(u)
		for k in range(self.num - 1):
			for v in range(self.n):
				if self.parent[k][v] == -1:
					self.parent[k + 1][v] = -1
					self.path[k + 1][v] = self.path[k][v]
				else:
					self.parent[k + 1][v] = self.parent[k][self.parent[k][v]]
					self.path[k + 1][v] = self.f(self.path[k][v], self.path[k][self.parent[k][v]])

	def getLCA(self, u, v):
		if self.depth[u] > self.depth[v]:
			(u, v) = (v, u)
		for k in range(self.num):
			if self.depth[v] - self.depth[u] >> k & 1:
				v = self.parent[k][v]
		if u == v:
			return u
		for k in reversed(range(self.num)):
			if self.parent[k][u] != self.parent[k][v]:
				u = self.parent[k][u]
				v = self.parent[k][v]
		return self.parent[0][u]

	def query(self, u, v):
		res = self.ide_ele
		if self.depth[u] > self.depth[v]:
			(u, v) = (v, u)
		for k in range(self.num):
			if self.depth[v] - self.depth[u] >> k & 1:
				res = self.f(self.path[k][v], res)
				v = self.parent[k][v]
		if u == v:
			return res
		for k in reversed(range(self.num)):
			if self.parent[k][u] != self.parent[k][v]:
				res = self.f(self.path[k][u], self.path[k][v], res)
				u = self.parent[k][u]
				v = self.parent[k][v]
		res = self.f(self.path[0][u], self.path[0][v], res)
		return res
import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m) = map(int, input().split())
edge = []
for i in range(m):
	(u, v, w) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	edge.append((u, v, w))
edge.sort(key=lambda x: x[2])
uf = UnionFind(n)
s = 0
g = [[] for i in range(n)]
nonused = []
for (u, v, w) in edge:
	if uf.Same(u, v):
		nonused.append((u, v, w))
		continue
	s += w
	uf.Unite(u, v)
	g[u].append((w, v))
	g[v].append((w, u))
lca = LCA(g, 0, max, 0)
ans = 0
for (u, v, w) in nonused:
	t = lca.query(u, v)
	if w == t:
		ans += 1
print(ans)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
EDGE = [list(map(int, input().split())) for i in range(m)]
EDGE.sort(key=lambda x: x[2])
WCHANGE = []
for i in range(1, m):
	if EDGE[i - 1][2] != EDGE[i][2]:
		WCHANGE.append(i)
WCHANGE.append(m)
Group = [i for i in range(n + 1)]

def find(x):
	while Group[x] != x:
		x = Group[x]
	return x

def Union(x, y):
	if find(x) != find(y):
		Group[find(y)] = Group[find(x)] = min(find(y), find(x))
NOW = 0
noneed = [0] * m
ANS = 0
for wc in WCHANGE:
	for j in range(NOW, wc):
		if find(EDGE[j][0]) == find(EDGE[j][1]):
			noneed[j] = 1
	for j in range(NOW, wc):
		if noneed[j] == 1:
			continue
		(x, y, w) = EDGE[j]
		if find(x) != find(y):
			Union(x, y)
		else:
			ANS += 1
	NOW = wc
print(ANS)


import collections as cc
import itertools as it
import bisect as bi
I = lambda : list(map(int, input().split()))
(n, m) = I()
ed = [I() for i in range(m)]
ed.sort(key=lambda x: x[2])
ch = []
for i in range(1, m):
	if ed[i - 1][2] != ed[i][2]:
		ch.append(i)
ch.append(m)
parent = [i for i in range(n + 1)]

def find(x):
	while x != parent[x]:
		x = parent[x]
	return x

def union(x, y):
	a = find(x)
	b = find(y)
	parent[a] = parent[b] = min(a, b)
cur = 0
cur = 0
no = [0] * m
ans = 0
for i in ch:
	for j in range(cur, i):
		if find(ed[j][0]) == find(ed[j][1]):
			no[j] = 1
	for j in range(cur, i):
		if no[j] == 1:
			continue
		(x, y, w) = ed[j]
		if find(x) != find(y):
			union(x, y)
		else:
			ans += 1
	cur = i
print(ans)