The legendary Farmer John is throwing a huge party, and animals from all over the world are hanging out at his house. His guests are hungry, so he instructs his cow Bessie to bring out the snacks! Moo!

There are $n$ snacks flavors, numbered with integers $1, 2, \ldots, n$. Bessie has $n$ snacks, one snack of each flavor. Every guest has exactly two favorite flavors. The procedure for eating snacks will go as follows:  First, Bessie will line up the guests in some way.  Then in this order, guests will approach the snacks one by one.  Each guest in their turn will eat all remaining snacks of their favorite flavor. In case no favorite flavors are present when a guest goes up, they become very sad.  

Help Bessie to minimize the number of sad guests by lining the guests in an optimal way.


-----Input-----

The first line contains integers $n$ and $k$ ($2 \le n \le 10^5$, $1 \le k \le 10^5$), the number of snacks and the number of guests. 

The $i$-th of the following $k$ lines contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$, $x_i \ne y_i$), favorite snack flavors of the $i$-th guest.


-----Output-----

Output one integer, the smallest possible number of sad guests.


-----Examples-----
Input
5 4
1 2
4 3
1 4
3 4

Output
1

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

Output
0



-----Note-----

In the first example, Bessie can order the guests like this: $3, 1, 2, 4$. Guest $3$ goes first and eats snacks $1$ and $4$. Then the guest $1$ goes and eats the snack $2$ only, because the snack $1$ has already been eaten. Similarly, the guest $2$ goes up and eats the snack $3$ only. All the snacks are gone, so the guest $4$ will be sad. 

In the second example, one optimal ordering is $2, 1, 3, 5, 4$. All the guests will be satisfied.

Difficulty: MEDIUM_HARD
Tags: Spanning trees

Graph algorithms

Graph traversal

Starter code:

Solutions:
def find_parent(u):
	if par[u] != u:
		par[u] = find_parent(par[u])
	return par[u]
(n, k) = map(int, input().split())
l = []
par = [0] + [i + 1 for i in range(n)]
g = []
rank = [1] * (n + 1)
ans = 0
for i in range(k):
	(a, b) = map(int, input().split())
	(z1, z2) = (find_parent(a), find_parent(b))
	if z1 != z2:
		par[z1] = z2
		rank[z2] += rank[z1]
		ans += 1
print(k - ans)


from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
import bisect

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def A():
	n = I()
	a = LI()
	a.sort()
	f = [1] * n
	p = 0
	ans = 0
	while p < n:
		while p < n and (not f[p]):
			p += 1
		if p == n:
			break
		ans += 1
		for i in range(n):
			if a[i] % a[p] == 0:
				f[i] = 0
	print(ans)
	return

def B():
	n = I()
	s = list(map(int, input()))
	g = LIR(n)
	ans = sum(s)
	for t in range(30000):
		for i in range(n):
			(ai, bi) = g[i]
			if t < bi:
				continue
			if (t - bi) % ai == 0:
				s[i] ^= 1
		su = sum(s)
		if ans < su:
			ans = su
	print(ans)
	return

def C():
	t = I()
	for _ in range(t):
		n = I()
		s = list(map(int, input()))
		mi = [s[-1]]
		for i in s[:-1][::-1]:
			mi.append(min(mi[-1], i))
		mi = mi[::-1]
		ans = [None] * n
		for i in range(n):
			if mi[i] == s[i]:
				ans[i] = 1
			else:
				ans[i] = 2
		q = [s[i] for i in range(n) if ans[i] > 1]
		p = [q[i] for i in range(len(q))]
		p.sort()
		if p == q:
			print(*ans, sep='')
		else:
			print('-')
	return

def D():

	def root(x):
		if x == par[x]:
			return x
		par[x] = root(par[x])
		return par[x]

	def unite(x, y):
		x = root(x)
		y = root(y)
		if rank[x] < rank[y]:
			par[x] = y
		else:
			par[y] = x
			if rank[x] == rank[y]:
				rank[x] += 1
	(n, k) = LI()
	par = [i for i in range(n)]
	rank = [0] * n
	for i in range(k):
		(x, y) = LI()
		x -= 1
		y -= 1
		if root(x) != root(y):
			unite(x, y)
	size = [0] * n
	for i in range(n):
		size[root(i)] += 1
	ans = 0
	for i in size:
		if i > 0:
			ans += i - 1
	print(k - ans)
	return

def E():
	return

def F():
	return

def G():
	return

def H():
	return
D()


import sys
input = sys.stdin.readline
(n, k) = list(map(int, input().split()))

class Union_Find:

	def __init__(self, num):
		self.par = [-1] * (num + 1)
		self.siz = [1] * (num + 1)

	def same_checker(self, x, y):
		return self.find(x) == self.find(y)

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

	def union(self, x, y):
		rx = self.find(x)
		ry = self.find(y)
		if rx != ry:
			if self.par[rx] < self.par[ry]:
				self.par[ry] = rx
				self.siz[rx] += self.siz[ry]
			elif self.par[rx] > self.par[ry]:
				self.par[rx] = ry
				self.siz[ry] += self.siz[rx]
			else:
				self.par[rx] -= 1
				self.par[ry] = rx
				self.siz[rx] += self.siz[ry]
		return

	def size(self, x):
		return self.siz[self.find(x)]
ans = 0
guest = Union_Find(n)
for i in range(k):
	(a, b) = list(map(int, input().split()))
	if guest.same_checker(a, b):
		ans += 1
	else:
		guest.union(a, b)
print(ans)


def find_set(v):
	if v == parent[v]:
		return v
	parent[v] = find_set(parent[v])
	return parent[v]

def union_sets(x, y):
	x = find_set(x)
	y = find_set(y)
	if x != y:
		if rank[x] < rank[y]:
			(x, y) = (y, x)
		parent[y] = x
		if rank[x] == rank[y]:
			rank[x] += 1
(n, k) = list(map(int, input().split()))
parent = [0] * n
rank = [0] * n
vis = [0] * n
for i in range(n):
	parent[i] = i
for _ in range(k):
	(x, y) = list(map(int, input().split()))
	union_sets(x - 1, y - 1)
c = 0
for i in range(n):
	if parent[i] == i:
		c += 1
print(k - n + c)


def find(people, N):
	dic = {}
	gr = [[] for _ in range(N + 1)]
	count = 0
	for (a, b) in people:
		(a, b) = sorted([a, b])
		if (a, b) in dic:
			count += 1
		else:
			dic[a, b] = 1
			gr[a] += [b]
			gr[b] += [a]
	checked = [0] * (N + 1)
	parent = [-1] * (N + 1)
	for i in range(1, N + 1):
		if checked[i] == 0:
			stack = [i]
			while stack:
				node = stack.pop()
				checked[node] = 2
				for v in gr[node]:
					if parent[node] == v:
						continue
					if checked[v] == 2:
						continue
					if checked[v] == 1:
						count += 1
					else:
						stack += [v]
						parent[v] = node
						checked[v] = 1
	return count
people = []
(n, k) = list(map(int, input().strip().split(' ')))
for _ in range(k):
	(a, b) = list(map(int, input().strip().split(' ')))
	people += [(a, b)]
print(find(people, n))


def find(u):
	if parent[u] == u:
		return u
	parent[u] = find(parent[u])
	return parent[u]

def union(a, b):
	u = parent[a]
	v = parent[b]
	if size[u] > size[v]:
		parent[v] = u
		size[u] += size[v]
		cnt[u] += cnt[v] + 1
	else:
		parent[u] = v
		size[v] += size[u]
		cnt[v] += cnt[u] + 1
(n, k) = map(int, input().split())
edges = []
for j in range(k):
	(u, v) = map(int, input().split())
	edges.append([u, v])
parent = [i for i in range(n + 1)]
size = [1 for i in range(n + 1)]
cnt = [0 for i in range(n + 1)]
for j in edges:
	(u, v) = (j[0], j[1])
	if find(u) == find(v):
		cnt[parent[u]] += 1
	else:
		union(u, v)
d = dict()
ans = 0
for j in range(1, n + 1):
	p = find(j)
	if p not in d.keys():
		ans += cnt[p] + 1 - size[p]
		d[p] = 1
print(ans)


import sys
from collections import defaultdict, deque
(n, k) = map(int, sys.stdin.readline().split())
fav = [[0, 0] for _ in range(k + 1)]
sweet = defaultdict(list)
for i in range(1, k + 1):
	(u, v) = map(int, sys.stdin.readline().split())
	fav[i] = [u, v]
	sweet[u].append(i)
	sweet[v].append(i)
vis = defaultdict(int)
viss = defaultdict(int)
ans = 0
for i in range(1, k + 1):
	if vis[i] == 0:
		q = deque()
		q.append(i)
		vis[i] = 1
		while q:
			a = q.pop()
			(c, d) = fav[a]
			if viss[c] == viss[d] == 1:
				ans += 1
				continue
			if viss[c] == 0:
				viss[c] = 1
				for j in sweet[c]:
					if vis[j] == 0:
						q.append(j)
						vis[j] += 1
			if viss[d] == 0:
				viss[d] = 1
				for j in sweet[d]:
					if vis[j] == 0:
						q.append(j)
						vis[j] += 1
print(ans)


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
snack = [tuple(sorted(map(int, input().split()))) for i in range(k)]
snack.sort()
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):
		(MIN, MAX) = sorted((find(y), find(x)))
		W[MIN] = W[find(x)] + W[find(y)]
		W[MAX] = 1
		Group[find(y)] = Group[find(x)] = MIN
W = [1] * (n + 1)
(a, b) = snack[0]
Union(a, b)
for i in range(1, k):
	if snack[i] == snack[i - 1]:
		continue
	(a, b) = snack[i]
	if find(a) != find(b):
		Union(a, b)
SUM = sum([w - 1 for w in W])
print(k - SUM)


(n, k) = map(int, input().split())
par = [int(i) for i in range(0, n)]

def find(x):
	if x != par[x]:
		par[x] = find(par[x])
	return par[x]
ss = 0
for _ in range(0, k):
	(a, b) = map(int, input().split())
	(aa, bb) = (find(a - 1), find(b - 1))
	if aa != bb:
		ss += 1
		par[aa] = bb
print(k - ss)


import sys
input = sys.stdin.readline
import collections
from collections import defaultdict

def bfs(graph, root):
	count = 0
	queue = collections.deque([root])
	visited.add(root)
	while queue:
		vertex = queue.popleft()
		for neighbour in graph[vertex]:
			if neighbour not in visited:
				count += 1
				visited.add(neighbour)
				queue.append(neighbour)
	return count
(n, k) = map(int, input().split())
graph = defaultdict(set)
for i in range(k):
	(one, two) = map(int, input().split())
	graph[one].add(two)
	graph[two].add(one)
visited = set()
maxfav = 0
for i in graph:
	if i not in visited:
		output = bfs(graph, i)
		maxfav += output
output = bfs(graph, maxfav)
print(k - maxfav)


import os
import sys
from io import BytesIO, IOBase
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')
from collections import defaultdict, deque
(n, k) = map(int, input().split())
graph = [set([]) for s in range(n)]
ind = defaultdict(list)
inverse = {}
for s in range(k):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	graph[x].add(y)
	graph[y].add(x)
	ind[frozenset([x, y])].append(s)
	inverse[s] = [x, y]
ans = []
vis = set([])
done = set([])
for s in range(n):
	if not s in vis:
		queue = deque([s])
		vis.add(s)
		while len(queue) > 0:
			v0 = queue.popleft()
			for i in graph[v0]:
				if not i in vis:
					queue.append(i)
					vis.add(i)
					gu = ind[frozenset([v0, i])].pop()
					ans.append(gu)
					done.add(gu)
for s in range(k):
	if not s in done:
		ans.append(s)
unhappy = 0
snacks = set([s for s in range(n)])
for s in range(len(ans)):
	s1 = inverse[ans[s]][0]
	s2 = inverse[ans[s]][1]
	if s1 in snacks or s2 in snacks:
		snacks.discard(s1)
		snacks.discard(s2)
	else:
		unhappy += 1
print(unhappy)


class dsu:

	def __init__(self, n):
		self.parent = [0] * (n + 1)
		self.size = [0] * (n + 1)

	def make_set(self, v):
		self.parent[v] = v
		self.size[v] = 1

	def union_set(self, a, b):
		a = self.find_set(a)
		b = self.find_set(b)
		if a != b:
			if self.size[a] < self.size[b]:
				(a, b) = (b, a)
			self.parent[b] = a
			self.size[a] += self.size[b]

	def find_set(self, v):
		if v == self.parent[v]:
			return v
		self.parent[v] = self.find_set(self.parent[v])
		return self.parent[v]
(n, k) = map(int, input().split())
xx = dsu(n)
for i in range(n):
	xx.make_set(i)
an = 0
for _ in range(k):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	if xx.find_set(x) == xx.find_set(y):
		an += 1
	else:
		xx.union_set(x, y)
print(an)


import sys
input = sys.stdin.readline
from collections import deque
(n, m) = map(int, input().split())
graph = [[] for i in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
ans = 0
v = [False] * n
for i in range(n):
	if not v[i]:
		size = 0
		q = deque([i])
		v[i] = True
		while q:
			node = q.popleft()
			size += 1
			for i in graph[node]:
				if not v[i]:
					v[i] = True
					q.append(i)
		ans += size - 1
print(m - ans)


def solve(graph: []):
	n = len(graph) - 1
	visited = [False] * (n + 1)
	guests = 0
	for i in range(1, n + 1):
		if not visited[i]:
			guests += Bfs(graph, visited, i) - 1
	return guests

def Bfs(graph: [], visited: [], id):
	(visited[id], queue, totalNodes) = (True, [], 0)
	queue.append(id)
	while queue:
		vid = queue.pop(0)
		totalNodes += 1
		for adj in graph[vid]:
			if not visited[adj]:
				visited[adj] = True
				queue.append(adj)
	return totalNodes
(n, k) = [int(x) for x in input().split()]
graph = [[] for _ in range(n + 1)]
for i in range(k):
	(u, v) = [int(x) for x in input().split()]
	graph[u].append(v)
	graph[v].append(u)
ans = k - solve(graph)
if ans < 0:
	ans = 0
print(ans)


(n, k) = list(map(int, input().split()))
parent = [i for i in range(n)]
rank = [1 for i in range(n)]

def find_parent(u):
	if parent[u] != u:
		parent[u] = find_parent(parent[u])
	return parent[u]
for i in range(k):
	(u, v) = list(map(int, input().split()))
	u = find_parent(u - 1)
	v = find_parent(v - 1)
	if u != v:
		parent[u] = v
		rank[v] += rank[u]
sat = 0
for i in range(n):
	if parent[i] == i:
		sat += rank[i] - 1
print(k - sat)


from collections import defaultdict
import sys
input = sys.stdin.readline
inf = 100000000000000000
mod = 998244353

def find(x):
	if fa[x] == x:
		return x
	else:
		fa[x] = find(fa[x])
		return fa[x]
(n, k) = map(int, input().split())
ans = 0
fa = [i for i in range(0, n + 1)]
for i in range(k):
	(x, y) = map(int, input().split())
	if find(x) == find(y):
		ans += 1
	else:
		fa[find(x)] = find(y)
print(ans)


import sys

def main():

	def input():
		return sys.stdin.readline()[:-1]
	(N, k) = map(int, input().split())
	parent = [k for k in range(N)]

	def find(x):
		if parent[x] == x:
			return x
		else:
			parent[x] = find(parent[x])
			return find(parent[x])

	def unite(x, y):
		parent[find(x)] = find(y)
	ans = 0
	for q in range(k):
		(x, y) = map(int, input().split())
		if find(x - 1) == find(y - 1):
			ans += 1
		else:
			unite(x - 1, y - 1)
	print(ans)
main()


import os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

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

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			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')
import sys

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'

def get_input(a=str):
	return a(input())

def get_int_input():
	return get_input(int)

def get_input_arr(a):
	return list(map(a, input().split()))

def get_int_input_arr():
	return get_input_arr(int)
from collections import defaultdict

class DSU:

	def __init__(self, N: int, has_meta: bool=False, meta_combine=None, default_meta_func=None) -> None:
		self._dsu = [0] * N
		self._parent = [x for x in range(N)]
		self._size = [1 for _ in range(N)]
		self._has_meta = has_meta
		if self._has_meta:
			self._meta_arr = [default_meta_func(x) for x in range(N)]
			self._meta_combine_func = meta_combine

	def find_set(self, ele: int) -> int:
		if self._parent[ele] == ele:
			return ele
		self._parent[ele] = self.find_set(self._parent[ele])
		return self._parent[ele]

	def get_represtatives_meta(self, ele: int):
		if not self._has_meta:
			return None
		return self._meta_arr[self.find_set(ele)]

	def get_ele_size(self, ele: int):
		return self._size[self.find_set(ele)]

	def get_ele_meta(self, ele: int):
		if not self._has_meta:
			return None
		return self._meta_arr[ele]

	def get_parent_set(self):
		st = set()
		for i in self._parent:
			if self._parent[i] == i:
				st.add(i)
		return st

	def union_set(self, ele1, ele2):
		p1 = self.find_set(ele1)
		p2 = self.find_set(ele2)
		if p1 == p2:
			return (False, self.get_ele_meta(p1))
		if self._size[p1] < self._size[p2]:
			(p1, p2) = (p2, p1)
		self._parent[p2] = p1
		self._size[p1] += self._size[p2]
		if self._has_meta:
			self._meta_arr[p1] = self._meta_combine_func(self._meta_arr[p1], self._meta_arr[p2])
		return (True, self.get_ele_meta(p1))

def solve():
	(n, k) = get_int_input_arr()
	dsu = DSU(n + 1)
	for _ in range(k):
		(v1, v2) = get_int_input_arr()
		dsu.union_set(v1, v2)
	st = 0
	parent_set = dsu.get_parent_set()
	for parent in parent_set:
		st += dsu._size[parent] - 1
	cout << k - st << endl

def main():
	solve()
main()


import sys

def find(u, a):
	if a[u] != -1:
		a[u] = find(a[u], a)
		return a[u]
	else:
		return u

def union(a, u, v, ct):
	x = find(u, a)
	y = find(v, a)
	if x == y:
		ct += 1
	else:
		a[x] = y
		ct = ct
	return ct
(n, k) = map(int, input().split())
a = [-1 for i in range(n + 1)]
count = 0
for i in range(k):
	(u, v) = map(int, input().split())
	count = union(a, u, v, count)
print(count)


class DisjointSetUnion:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n

	def find(self, a):
		acopy = a
		while a != self.parent[a]:
			a = self.parent[a]
		while acopy != a:
			(self.parent[acopy], acopy) = (a, self.parent[acopy])
		return a

	def union(self, a, b):
		(a, b) = (self.find(a), self.find(b))
		if a != b:
			if self.size[a] < self.size[b]:
				(a, b) = (b, a)
			self.num_sets -= 1
			self.parent[b] = a
			self.size[a] += self.size[b]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets
(n, m) = map(int, input().split())
A = DisjointSetUnion(n)
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	A.union(a, b)
print(m - (n - len(A)))


import sys
input = sys.stdin.buffer.readline
from collections import defaultdict as d

class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))

	def find(self, a):
		acopy = a
		while a != self.parent[a]:
			a = self.parent[a]
		while acopy != a:
			(self.parent[acopy], acopy) = (a, self.parent[acopy])
		return a

	def union(self, a, b):
		self.parent[self.find(b)] = self.find(a)
(n, k) = [int(x) for x in input().split()]
uf = UnionFind(n)
guests = []
for _ in range(k):
	(x, y) = [int(z) for z in input().split()]
	x -= 1
	y -= 1
	uf.union(x, y)
	guests.append([x, y])
roots = set()
groupSnackSizes = d(lambda : 0)
for i in range(n):
	root = uf.find(i)
	groupSnackSizes[root] += 1
	roots.add(root)
groupGuestSizes = d(lambda : 0)
for (x, y) in guests:
	groupGuestSizes[uf.find(x)] += 1
ans = k
for root in roots:
	ans -= min(groupGuestSizes[root], groupSnackSizes[root] - 1)
print(ans)


class UnionFind:

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

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

	def union(self, x, y):
		px = self.find(x)
		py = self.find(y)
		if px != py:
			if self.rank[px] == self.rank[py]:
				self.rank[px] += 1
			elif self.rank[px] < self.rank[py]:
				(px, py) = (py, px)
			self.par[py] = px
			self.size[px] += self.size[py]

	def same_check(self, x, y):
		return self.find(x) == self.find(y)
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
(n, k) = map(int, input().split())
uf = UnionFind(n)
Edges = set()
for _ in range(k):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	if a > b:
		(a, b) = (b, a)
	Edges.add((a, b))
for (a, b) in Edges:
	uf.union(a, b)
P = set()
for i in range(n):
	P.add(uf.find(i))
num = 0
for p in P:
	num += uf.size[p] - 1
print(k - num)


from collections import deque

def dfs(s, vis, items):
	ans = 0
	q = deque()
	q.append(s)
	vis[s] = True
	while len(q) > 0:
		u = q.popleft()
		for v in items[u]:
			if not vis[v]:
				vis[v] = True
				q.append(v)
				ans += 1
	return ans
(n, k) = map(int, input().split())
arr = [map(int, input().split()) for _ in range(k)]
items = [[] for _ in range(n + 1)]
for (x, y) in arr:
	items[x].append(y)
	items[y].append(x)
vis = [False for _ in range(n + 1)]
ans = k
for (i, a) in enumerate(items[1:]):
	if not vis[i]:
		ans -= dfs(i, vis, items)
print(ans)


(n, k) = list(map(int, input().split()))
parent = [i for i in range(n)]
rank = [1 for i in range(n)]

def find(u):
	if parent[u] != u:
		parent[u] = find(parent[u])
	return parent[u]
for _ in range(k):
	(u, v) = list(map(int, input().split()))
	u -= 1
	v -= 1
	a = find(u)
	b = find(v)
	if a != b:
		parent[a] = b
		rank[b] += rank[a]
ans = 0
for i in range(n):
	if parent[i] == i:
		ans += rank[i] - 1
print(k - ans)


import sys
input = sys.stdin.readline
from collections import deque
(N, K) = list(map(int, input().split()))
X = [[] for i in range(N)]
for i in range(K):
	(x, y) = list(map(int, input().split()))
	X[x - 1].append(y - 1)
	X[y - 1].append(x - 1)
mi = 10 ** 6
mii = 0
for i in range(N):
	if len(X) and len(X) < mi:
		mi = len(X)
		mii = i
Y = [(len(X[i]), i) for i in range(N) if len(X[i])]
Y = sorted(Y)
Q = [y[1] for y in Y]
P = [-1] * N
D = [0] * N
ans = 0
while Q:
	i = Q.pop()
	for a in X[i]:
		if D[a] == 0 or D[i] == 0:
			ans += 1
			D[a] = 1
			D[i] = 1
			if a != P[i]:
				P[a] = i
				X[a].remove(i)
				Q.append(a)
print(K - ans)


(n, m) = list(map(int, input().split()))
gr = [set() for i in range(n)]
for i in range(m):
	(a, b) = list(map(int, input().split()))
	gr[a - 1].add(b - 1)
	gr[b - 1].add(a - 1)
v = [False for i in range(n)]
an = 0
for i in range(n):
	if v[i]:
		continue
	s = [i]
	d = 0
	v[i] = True
	while s:
		x = s.pop()
		d += 1
		for j in gr[x]:
			if v[j]:
				continue
			v[j] = True
			s.append(j)
	an += d - 1
print(m - an)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from functools import cmp_to_key
from heapq import *
from math import gcd, factorial, floor, ceil
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
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')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = 998244353

def bfs(g, st, visited):
	queue = deque([])
	queue.append(st)
	new = []
	while len(queue) != 0:
		s = queue.popleft()
		new.append(s)
		for i in g[s]:
			if visited[i] == 0:
				global ans
				ans += 1
				visited[i] = 1
				queue.append(i)

def solve(case):
	(n, k) = sep()
	a = {}
	g = [[] for i in range(n)]
	for i in range(k):
		(x, y) = sep()
		x -= 1
		y -= 1
		g[x].append(y)
		g[y].append(x)
	vis = [0] * n
	col = 1
	for i in range(n):
		if not vis[i]:
			vis[i] = True
			q = deque([i])
			bfs(g, i, vis)
	print(k - ans)
ans = 0
testcase(1)


root = []

def find(u):
	if root[u] != u:
		root[u] = find(root[u])
	return root[u]
dem = 0
(n, k) = [int(i) for i in input().split()]
root = [int(_) for _ in range(n + 1)]
for i in range(1, n + 1):
	root[i] = i
for i in range(k):
	(x, y) = [int(_) for _ in input().split()]
	root_x = find(x)
	root_y = find(y)
	if root_x != root_y:
		root[root_x] = root[root_y]
	else:
		dem = dem + 1
print(dem)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import defaultdict
dict1 = {}

def dfs(node):
	stack = [[node, -1]]
	vis[node] = 1
	ans = 0
	while stack:
		temp = stack.pop()
		cur = temp[0]
		par = temp[1]
		for j in edge[cur]:
			if vis[j] == 0:
				stack.append([j, cur])
				vis[j] = 1
			elif j != par and (j, cur) not in dict1.keys():
				ans += 1
				dict1[cur, j] = 1
	return ans
(n, k) = list(map(int, input().split()))
edge = defaultdict(list)
lis = [0] * (n + 1)
for i in range(k):
	(u, v) = list(map(int, input().split()))
	lis[u] = 1
	lis[v] = 1
	edge[u].append(v)
	edge[v].append(u)
ans = 0
vis = [0] * (n + 1)
arr = []
l = 0
for i in range(1, n + 1):
	if lis[i] == 1:
		arr.append(i)
		l += 1
for i in range(l):
	if vis[arr[i]] == 0:
		ans += dfs(arr[i])
print(ans)


(n, m) = map(int, input().split())
p = [i for i in range(1, n + 1)]
p = [0] + p
size = [1] * (n + 1)

def get(a):
	if p[a] != a:
		p[a] = get(p[a])
	return p[a]

def union(a, b):
	a = get(a)
	b = get(b)
	if size[a] > size[b]:
		(a, b) = (b, a)
	p[a] = b
	size[b] += size[a]
for i in range(m):
	(a, b) = map(int, input().split())
	if get(a) != get(b):
		union(a, b)
ans = 0
s = set()
for i in range(1, n + 1):
	i = get(i)
	if i not in s:
		s.add(i)
		ans += size[i] - 1
print(m - ans)


from collections import defaultdict
import sys
import typing

class DSU:

	def __init__(self, n: int=0) -> None:
		self._n = n
		self.parent_or_size = [-1] * n

	def merge(self, a: int, b: int) -> int:
		assert 0 <= a < self._n
		assert 0 <= b < self._n
		x = self.leader(a)
		y = self.leader(b)
		if x == y:
			return x
		if -self.parent_or_size[x] < -self.parent_or_size[y]:
			(x, y) = (y, x)
		self.parent_or_size[x] += self.parent_or_size[y]
		self.parent_or_size[y] = x
		return x

	def same(self, a: int, b: int) -> bool:
		assert 0 <= a < self._n
		assert 0 <= b < self._n
		return self.leader(a) == self.leader(b)

	def leader(self, a: int) -> int:
		assert 0 <= a < self._n
		parent = self.parent_or_size[a]
		while parent >= 0:
			if self.parent_or_size[parent] < 0:
				return parent
			(self.parent_or_size[a], a, parent) = (self.parent_or_size[parent], self.parent_or_size[parent], self.parent_or_size[self.parent_or_size[parent]])
		return a

	def size(self, a: int) -> int:
		assert 0 <= a < self._n
		return -self.parent_or_size[self.leader(a)]

	def groups(self) -> typing.List[typing.List[int]]:
		leader_buf = [self.leader(i) for i in range(self._n)]
		result: typing.List[typing.List[int]] = [[] for _ in range(self._n)]
		for i in range(self._n):
			result[leader_buf[i]].append(i)
		return list(filter(lambda r: r, result))

def input():
	return sys.stdin.readline().rstrip()

def slv():
	(n, k) = map(int, input().split())
	dsu = DSU(n)
	Edge = []
	for i in range(k):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		Edge.append((u, v))
		dsu.merge(u, v)
	ans = k - n + len(set([dsu.leader(i) for i in range(n)]))
	print(ans)
	return

def main():
	t = 1
	for i in range(t):
		slv()
	return
main()


def find(x):
	if par[x] == x:
		return x
	par[x] = find(par[x])
	return par[x]

def union(a, b):
	la = find(a)
	lb = find(b)
	if la != lb:
		if size[la] > size[lb]:
			temp = la
			la = lb
			lb = temp
		size[lb] += size[la]
		size[la] = 0
		par[la] = lb
(n, k) = map(int, input().split())
par = [i for i in range(n + 1)]
size = [1 for i in range(n + 1)]
for i in range(k):
	(a, b) = map(int, input().split())
	union(a, b)
count = 0
for i in range(1, n + 1):
	count += max(0, size[i] - 1)
print(k - count)


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial, gcd
from collections import deque
from bisect import bisect_left
(n, k) = map(int, input().split())
graph = {i: set() for i in range(n)}
for i in range(k):
	(a, b) = map(int, input().split())
	graph[a - 1].add(b - 1)
	graph[b - 1].add(a - 1)
visited = [0] * n
count = 0
for i in range(n):
	if visited[i] == 0:
		count += 1
		stack = [i]
		while stack:
			x = stack.pop()
			visited[x] = 1
			for i in graph[x]:
				if visited[i] == 0:
					stack.append(i)
					visited[i] = 1
print(k - (n - count))


from collections import deque, Counter
import array
from itertools import combinations, permutations
from math import sqrt
import unittest

def read_int():
	return int(input().strip())

def read_int_array():
	return [int(i) for i in input().strip().split(' ')]
(n, k) = read_int_array()
adj = [[] for _ in range(n)]
edges = set()
for _ in range(k):
	(x, y) = read_int_array()
	(x, y) = (y, x) if y < x else (x, y)
	if (x, y) not in edges:
		edges.add((x, y))
		adj[x - 1] += [y - 1]
		adj[y - 1] += [x - 1]
marked = set()

def bfs(s):
	tree = []
	queue = [s]
	count = 0
	while queue:
		v = queue.pop()
		if v in marked:
			continue
		tree += [v]
		count += 1
		marked.add(v)
		for w in adj[v]:
			if w not in marked:
				queue += [w]
	return count
count = 0
for v in range(n):
	if v not in marked:
		m = bfs(v)
		count += m - 1
print(k - count)


class UnionFind:

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

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

	def same_check(self, x, y):
		return self.find(x) == self.find(y)

	def get_size(self, x):
		return self.size[self.find(x)]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			self.edge[x] += 1
			return
		if self.rank[x] < self.rank[y]:
			self.par[x] = y
			self.size[y] += self.size[x]
			self.edge[y] += self.edge[x] + 1
		else:
			self.par[y] = x
			self.size[x] += self.size[y]
			self.edge[x] += self.edge[y] + 1
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1
(n, k) = [int(item) for item in input().split()]
UF = UnionFind(2 * 10 ** 5)
for i in range(k):
	(a, b) = [int(item) for item in input().split()]
	a -= 1
	b -= 1
	UF.union(a, b)
seen = [False] * (2 * 10 ** 5)
ans = 0
for i in range(2 * 10 ** 5):
	par = UF.find(i)
	if seen[par]:
		continue
	if UF.edge[par] == 0:
		continue
	else:
		ans += UF.edge[par] - (UF.size[par] - 1)
	seen[par] = True
print(ans)


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

def union(a, b, parent, size):
	a_par = find(a, parent)
	b_par = find(b, parent)
	if a_par == b_par:
		return 1
	if size[a_par] < size[b_par]:
		parent[a_par] = b_par
		size[b_par] += size[a_par]
	else:
		parent[b_par] = a_par
		size[a_par] += size[b_par]
	return 0

def main():
	(N, Q) = map(int, input().split())
	parent = [i for i in range(N + 1)]
	size = [1 for _ in range(N + 1)]
	sad = 0
	for i in range(Q):
		(u, v) = map(int, input().split())
		sad += union(u, v, parent, size)
	print(sad)
main()


import sys
input = sys.stdin.readline
from collections import defaultdict

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

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

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]
(n, k) = map(int, input().split())
fav = [list(map(int, input().split())) for i in range(k)]
ans = 0
uf = UnionFind(n)
for (x, y) in fav:
	x -= 1
	y -= 1
	if uf.same(x, y):
		ans += 1
	uf.union(x, y)
print(ans)


import os
import sys
from io import BytesIO, IOBase

def find(z, p):
	a = []
	while p[z] != z:
		a.append(z)
		z = p[z]
	for i in a:
		p[i] = z
	return z

def union(p, s, x, y):
	(x, y) = (find(x, p), find(y, p))
	if x != y:
		if s[x] > s[y]:
			s[x] += s[y]
			p[y] = p[x]
		else:
			s[y] += s[x]
			p[x] = p[y]

def main():
	(n, k) = map(int, input().split())
	(p, s) = ([i for i in range(n + 1)], [1] * (n + 1))
	for i in range(k):
		(x, y) = map(int, input().split())
		union(p, s, x, y)
	print(max(0, k - (n - len(set((find(i, p) for i in range(1, n + 1)))))))
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()


from collections import deque
(n, m) = map(int, input().split())
graph = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
vis = [0] * n
c = 0
for i in range(n):
	if not vis[i]:
		c += 1
		queue = [i]
		queue = deque(queue)
		while len(queue) != 0:
			e = queue.popleft()
			vis[e] = 1
			for i in graph[e]:
				if not vis[i]:
					queue.append(i)
					vis[i] = 1
print(m - (n - c))


def flood_fill(adj_lists, colors, i, color):
	q = set()
	q.add(i)
	while len(q) > 0:
		j = q.pop()
		if colors[j] is None:
			colors[j] = color
			for k in adj_lists[j]:
				q.add(k)

def main():
	(n, k) = list(map(int, input().split()))
	adj_lists = [[] for _ in range(n)]
	for _ in range(k):
		(a, b) = list(map(int, input().split()))
		a -= 1
		b -= 1
		adj_lists[a].append(b)
		adj_lists[b].append(a)
	colors = [None for _ in range(n)]
	num_colors = 0
	for i in range(n):
		if colors[i] is None:
			flood_fill(adj_lists, colors, i, num_colors)
			num_colors += 1
	print(k - n + num_colors)

def __starting_point():
	main()
__starting_point()


from collections import deque

def flood_fill(adj_lists, colors, i, color):
	q = deque()
	q.append(i)
	while len(q) > 0:
		j = q.pop()
		if colors[j] is None:
			colors[j] = color
			q.extend(adj_lists[j])

def main():
	(n, k) = list(map(int, input().split()))
	adj_lists = [[] for _ in range(n)]
	for _ in range(k):
		(a, b) = list(map(int, input().split()))
		a -= 1
		b -= 1
		adj_lists[a].append(b)
		adj_lists[b].append(a)
	colors = [None for _ in range(n)]
	num_colors = 0
	for i in range(n):
		if colors[i] is None:
			flood_fill(adj_lists, colors, i, num_colors)
			num_colors += 1
	print(k - n + num_colors)

def __starting_point():
	main()
__starting_point()


from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 7)
import threading
threading.stack_size(2 ** 27)

def iin():
	return int(stdin.readline())

def lin():
	return list(map(int, stdin.readline().split()))

class Disjoint_set:

	def __init__(sf, n):
		sf.parent = {i: i for i in range(1, n + 1)}

	def union(sf, x, y):
		sf.link(sf.find_set(x), sf.find_set(y))

	def link(sf, val1, val2):
		sf.parent[val1] = val2

	def find_set(sf, val):
		if sf.parent[val] != val:
			sf.parent[val] = sf.find_set(sf.parent[val])
			return sf.parent[val]
		else:
			return val
from collections import defaultdict

def main():
	(n, k) = lin()
	a = [lin() for i in range(k)]
	da = Disjoint_set(n)
	for (i, j) in a:
		da.union(i, j)
	ch = defaultdict(int)
	for i in range(1, n + 1):
		ch[da.find_set(i)] += 1
	ans = 0
	for i in ch:
		if ch[i]:
			ans += ch[i] - 1
	print(k - ans)
try:

	def __starting_point():
		threading.Thread(target=main).start()
except Exception as e:
	print(e)
__starting_point()


import os
import sys
from io import BytesIO, IOBase

def main():
	(n, m) = [int(j) for j in input().split()]
	adj = [set() for i in range(n)]
	for i in range(m):
		(l, r) = [int(j) - 1 for j in input().split()]
		adj[l].add(r)
		adj[r].add(l)
	ct = 0
	visited = [False for i in range(n)]
	for i in range(n):
		if visited[i] == False:
			stack = [i]
			tct = 1
			while stack:
				p = stack.pop()
				visited[p] = True
				for j in adj[p]:
					if visited[j] == False:
						visited[j] = True
						tct += 1
						stack.append(j)
			ct += max(0, tct - 1)
	print(m - ct)
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()


def find(x):
	x1 = x
	while p[x] != x:
		x = p[x]
	while p[x1] != x1:
		x2 = p[x1]
		p[x1] = x
		x1 = x2
	return x
inp = lambda : map(int, input().split())
(n, k) = inp()
edges = []
for i in range(k):
	(x, y) = inp()
	edges.append([x - 1, y - 1])
p = [i for i in range(n)]
ans = 0
for i in edges:
	p1 = find(i[0])
	p2 = find(i[1])
	if p1 == p2:
		ans += 1
	else:
		p[p1] = p2
print(ans)


class UnionFind:

	def __init__(self, n):
		self.count = n
		self.parent = [i for i in range(n)]

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

	def union(self, x, y):
		px = self.find(x)
		py = self.find(y)
		if px == py:
			return False
		else:
			self.count -= 1
			self.parent[px] = py
			return True

def cowAndSnacks(fav, m):
	uf = UnionFind(m)
	sad = 0
	for guest in fav:
		[a, b] = fav[guest]
		if uf.union(a, b) == False:
			sad += 1
	return sad
line = input()
[n, k] = list(map(int, line.split(' ')))
fav = {}
snacks = {}
for guest in range(k):
	f = list(map(int, input().split(' ')))
	s = []
	for snack in f:
		if snack in snacks:
			new_idx = snacks[snack]
		else:
			new_idx = len(snacks)
			snacks[snack] = new_idx
		s.append(new_idx)
	fav[guest] = s
m = len(snacks)
res = cowAndSnacks(fav, m)
print(res)


from queue import Queue
(N, K) = list(map(int, input().strip().split(' ')))
snacks = [[] for i in range(N + 1)]
visited = [False for i in range(N + 1)]
for k in range(K):
	(a, b) = list(map(int, input().strip().split(' ')))
	snacks[a].append(b)
	snacks[b].append(a)
q = Queue()
components = 0
for here in range(1, N + 1):
	if visited[here] == False:
		visited[here] = True
		for there in snacks[here]:
			if visited[there] == False:
				visited[there] = True
				q.put(there)
		while q.qsize() > 0:
			here = q.get()
			for there in snacks[here]:
				if visited[there] == False:
					visited[there] = True
					q.put(there)
		components += 1
ret = K - (N - components)
print(ret)


import sys
(n, k) = [int(i) for i in sys.stdin.readline().split()]
gwl = []
for i in range(n + 1):
	gwl.append([])
data = []
for kk in range(k):
	d = [int(i) for i in sys.stdin.readline().split()]
	gwl[d[0]].append(kk)
	gwl[d[1]].append(kk)
	data.append(d)
one = set()
two = set(range(k))
sn = [1] * (n + 1)
doub = [1] * k
ans = 0
while True:
	if one:
		ans += 1
		q = one.pop()
		d = data[q]
		if sn[d[0]]:
			sn[d[0]] = 0
			for oth in gwl[d[0]]:
				if doub[oth]:
					two.remove(oth)
					one.add(oth)
					doub[oth] = 0
				else:
					one.discard(oth)
		else:
			sn[d[1]] = 0
			for oth in gwl[d[1]]:
				if doub[oth]:
					two.remove(oth)
					one.add(oth)
					doub[oth] = 0
				else:
					one.discard(oth)
	elif two:
		ans += 1
		q = two.pop()
		doub[q] = 0
		d = data[q]
		for w in range(2):
			sn[d[w]] = 0
			for oth in gwl[d[w]]:
				if doub[oth]:
					two.remove(oth)
					one.add(oth)
					doub[oth] = 0
				else:
					one.discard(oth)
	else:
		break
print(k - ans)


class UnionFind:

	def __init__(self, n):
		self.n = n
		self.root = [-1] * (n + 1)
		self.rnk = [0] * (n + 1)

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

	def Unite(self, x, y):
		x = self.Find_Root(x)
		y = self.Find_Root(y)
		if x == y:
			return
		elif self.rnk[x] > self.rnk[y]:
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if self.rnk[x] == self.rnk[y]:
				self.rnk[y] += 1

	def isSameGroup(self, x, y):
		return self.Find_Root(x) == self.Find_Root(y)

	def Count(self, x):
		return -self.root[self.Find_Root(x)]
import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(K)]
uni = UnionFind(N + 1)
for (x, y) in XY:
	uni.Unite(x, y)
ans = K
roots = set()
for n in range(1, N + 1):
	r = uni.Find_Root(n)
	if not r in roots:
		roots.add(r)
		ans -= uni.Count(r) - 1
print(ans)


import sys
input = sys.stdin.readline
import collections

class UnionFind:

	def __init__(self):
		self.parent = {}

	def add(self, e):
		self.parent[e] = e

	def find(self, e):
		p = e
		while self.parent[p] != p:
			p = self.parent[p]
		self.parent[e] = p
		return p

	def union(self, e1, e2):
		self.parent[self.find(e1)] = self.find(e2)

	def getDepth(self, e):
		depth = 0
		p = e
		while self.parent[p] != p:
			depth += 1
			p = self.parent[p]
		return depth

def minGuest(n, guests):
	uf = UnionFind()
	for e in range(1, n + 1):
		uf.add(e)
	for (e1, e2) in guests:
		uf.union(e1, e2)
	m = collections.defaultdict(int)
	for e in range(1, n + 1):
		m[uf.find(e)] += 1
	ne = 0
	for (_, cnt) in m.items():
		ne += cnt - 1
	return len(guests) - ne

def main():
	(n, k) = input().split()
	guests = []
	for _ in range(int(k)):
		(a, b) = input().split()
		guests.append([int(a), int(b)])
	print(minGuest(int(n), guests))
main()


from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
import sys
input = sys.stdin.buffer.readline
from collections import defaultdict as d

@bootstrap
def dfs(node, root):
	groupSnackSizes[root] += 1
	snackRoot[node] = root
	for nex in snackAdj[node]:
		if snackRoot[nex] == -1:
			yield dfs(nex, root)
	yield None
(n, k) = [int(x) for x in input().split()]
guests = []
snackAdj = [set() for _ in range(n)]
for _ in range(k):
	(x, y) = [int(z) for z in input().split()]
	x -= 1
	y -= 1
	snackAdj[x].add(y)
	snackAdj[y].add(x)
	guests.append([x, y])
roots = set()
snackRoot = [-1 for _ in range(n)]
groupSnackSizes = d(lambda : 0)
for i in range(n):
	if snackRoot[i] == -1:
		roots.add(i)
		dfs(i, i)
groupGuestSizes = d(lambda : 0)
for (x, y) in guests:
	groupGuestSizes[snackRoot[x]] += 1
ans = k
for root in roots:
	ans -= min(groupGuestSizes[root], groupSnackSizes[root] - 1)
print(ans)


from queue import Queue
(n, k) = map(int, input().split())
a = [tuple(sorted(list(map(lambda x: int(x) - 1, input().split())))) for i in range(k)]
a = list(set(a))
a.sort()
edges = [[] for i in range(n)]
for i in a:
	edges[i[0]].append(i[1])
	edges[i[1]].append(i[0])
ans = 0
visited = [False for i in range(n)]
queue = Queue(maxsize=n)
for j in range(len(a)):
	if not visited[a[j][0]] and visited[a[j][1]]:
		visited[a[j][0]] = True
		s = a[j][0]
		ans += 1
		queue.put(s)
		while not queue.empty():
			s = queue.get()
			for i in edges[s]:
				if visited[i] == False:
					queue.put(i)
					visited[i] = True
					ans += 1
	elif visited[a[j][0]] and (not visited[a[j][1]]):
		visited[a[j][1]] = True
		s = a[j][1]
		ans += 1
		queue.put(s)
		while not queue.empty():
			s = queue.get()
			for i in edges[s]:
				if visited[i] == False:
					queue.put(i)
					visited[i] = True
					ans += 1
	elif not visited[a[j][0]] and (not visited[a[j][1]]):
		visited[a[j][0]] = True
		visited[a[j][1]] = True
		ans += 1
		s = a[j][0]
		queue.put(s)
		while not queue.empty():
			s = queue.get()
			for i in edges[s]:
				if visited[i] == False:
					queue.put(i)
					visited[i] = True
					ans += 1
		s = a[j][1]
		queue.put(s)
		while not queue.empty():
			s = queue.get()
			for i in edges[s]:
				if visited[i] == False:
					queue.put(i)
					visited[i] = True
					ans += 1
print(abs(k - ans))


(n, k) = map(int, input().split())
graph = {i: set() for i in range(1, n + 1)}
for _ in range(k):
	(u, v) = map(int, input().split())
	graph[u].add(v)
	graph[v].add(u)
ans = 0
used = [0] * (n + 1)
for v in range(1, n + 1):
	if used[v] == 0:
		ans += 1
		S = [v]
		while S:
			ver = S.pop()
			for u in graph[ver]:
				if used[u] == 0:
					S.append(u)
					used[u] = 1
print(k - n + ans)


def find(x):
	if parent[x] == x:
		return x
	else:
		parent[x] = find(parent[x])
		return parent[x]
(n, k) = map(int, input().split())
parent = list(range(n + 1))
ans = 0
for _ in range(1, k + 1):
	(a, b) = map(int, input().split())
	ax = find(a)
	bx = find(b)
	if ax == bx:
		ans += 1
	else:
		parent[ax] = bx
print(ans)


(n, k) = map(int, input().split())
guests = []
items = [set() for _ in range(n + 2)]
for _ in range(k):
	(x, y) = map(int, input().split())
	guests.append([x, y])
	items[x].add(_)
	items[y].add(_)
taken = [False] * (n + 2)
rem = set((_ for _ in range(k)))
ans = 0
while len(rem) > 0:
	r = rem.pop()
	if taken[guests[r][0]] == True and taken[guests[r][1]] == True:
		ans += 1
		continue
	temp = set()
	if taken[guests[r][0]] == False:
		temp.add(guests[r][0])
	if taken[guests[r][1]] == False:
		temp.add(guests[r][1])
	taken[guests[r][0]] = True
	taken[guests[r][1]] = True
	while len(temp) > 0:
		t = temp.pop()
		for i in items[t]:
			if i in rem:
				rem.remove(i)
				if taken[guests[i][0]] == True and taken[guests[i][1]] == True:
					ans += 1
					continue
				if taken[guests[i][0]] == False:
					taken[guests[i][0]] = True
					temp.add(guests[i][0])
				if taken[guests[i][1]] == False:
					taken[guests[i][1]] = True
					temp.add(guests[i][1])
print(ans)


import sys
input = sys.stdin.buffer.readline
from collections import defaultdict as d
(n, k) = [int(x) for x in input().split()]
guests = []
snackAdj = [set() for _ in range(n)]
for _ in range(k):
	(x, y) = [int(z) for z in input().split()]
	x -= 1
	y -= 1
	snackAdj[x].add(y)
	snackAdj[y].add(x)
	guests.append([x, y])
roots = set()
snackRoot = [-1 for _ in range(n)]
groupSnackSizes = d(lambda : 0)
for i in range(n):
	if snackRoot[i] == -1:
		roots.add(i)
		st = [i]
		while st:
			node = st.pop()
			groupSnackSizes[i] += 1
			snackRoot[node] = i
			for nex in snackAdj[node]:
				if snackRoot[nex] == -1:
					snackRoot[nex] = i
					st.append(nex)
	else:
		continue
groupGuestSizes = d(lambda : 0)
for (x, y) in guests:
	groupGuestSizes[snackRoot[x]] += 1
ans = k
for root in roots:
	ans -= min(groupGuestSizes[root], groupSnackSizes[root] - 1)
print(ans)


(n, ne) = map(int, input().split())
tr = [[] for __ in range(n)]
for __ in range(ne):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	tr[u].append(v)
	tr[v].append(u)
visited = [0] * n
r = 0
for i in range(n):
	if visited[i]:
		continue
	q = [i]
	visited[i] = 1
	for u in q:
		for v in tr[u]:
			if not visited[v]:
				visited[v] = 1
				q.append(v)
				r += 1
print(ne - r)


import sys
input = sys.stdin.readline

class Unionfind:

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

	def root(self, x):
		p = x
		while not self.par[p] < 0:
			p = self.par[p]
		while x != p:
			tmp = x
			x = self.par[x]
			self.par[tmp] = p
		return p

	def unite(self, x, y):
		(rx, ry) = (self.root(x), self.root(y))
		if rx == ry:
			return False
		if self.rank[rx] < self.rank[ry]:
			(rx, ry) = (ry, rx)
		self.par[rx] += self.par[ry]
		self.par[ry] = rx
		if self.rank[rx] == self.rank[ry]:
			self.rank[rx] += 1

	def is_same(self, x, y):
		return self.root(x) == self.root(y)

	def count(self, x):
		return -self.par[self.root(x)]
(n, k) = map(int, input().split())
uf = Unionfind(n)
for _ in range(k):
	(x, y) = map(int, input().split())
	uf.unite(x - 1, y - 1)
root = set((uf.root(i) for i in range(n)))
ans = k - sum((uf.count(r) - 1 for r in root))
print(ans)


from sys import stdin
(n, k) = tuple((int(x) for x in stdin.readline().split()))
dic = {}
ans = 0
for i in range(k):
	(a, b) = tuple((int(x) for x in stdin.readline().split()))
	a -= 1
	b -= 1
	if a not in dic:
		dic[a] = set((b,))
	else:
		dic[a].add(b)
	if b not in dic:
		dic[b] = set((a,))
	else:
		dic[b].add(a)
for i in range(n):
	if i in dic:
		lst = [i]
		s = set((i,))
		for src in lst:
			if src in dic:
				for dest in dic[src]:
					if dest in dic and dest not in s:
						lst.append(dest)
						s.add(dest)
						ans += 1
				del dic[src]
print(k - ans)