Berland has n cities connected by m bidirectional roads. No road connects a city to itself, and each pair of cities is connected by no more than one road. It is not guaranteed that you can get from any city to any other one, using only the existing roads.

The President of Berland decided to make changes to the road system and instructed the Ministry of Transport to make this reform. Now, each road should be unidirectional (only lead from one city to another).

In order not to cause great resentment among residents, the reform needs to be conducted so that there can be as few separate cities as possible. A city is considered separate, if no road leads into it, while it is allowed to have roads leading from this city.

Help the Ministry of Transport to find the minimum possible number of separate cities after the reform.


-----Input-----

The first line of the input contains two positive integers, n and m — the number of the cities and the number of roads in Berland (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000). 

Next m lines contain the descriptions of the roads: the i-th road is determined by two distinct integers x_{i}, y_{i} (1 ≤ x_{i}, y_{i} ≤ n, x_{i} ≠ y_{i}), where x_{i} and y_{i} are the numbers of the cities connected by the i-th road.

It is guaranteed that there is no more than one road between each pair of cities, but it is not guaranteed that from any city you can get to any other one, using only roads.


-----Output-----

Print a single integer — the minimum number of separated cities after the reform.


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

Output
1

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

Output
0

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

Output
1



-----Note-----

In the first sample the following road orientation is allowed: $1 \rightarrow 2$, $1 \rightarrow 3$, $3 \rightarrow 4$.

The second sample: $1 \rightarrow 2$, $3 \rightarrow 1$, $2 \rightarrow 3$, $2 \rightarrow 5$, $3 \rightarrow 4$.

The third sample: $1 \rightarrow 2$, $2 \rightarrow 3$, $4 \rightarrow 5$, $5 \rightarrow 6$, $6 \rightarrow 4$.

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Greedy algorithms

Spanning trees

Data structures
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
read = lambda : map(int, input().split())
(n, m) = read()
g = [list() for i in range(n + 1)]
f = [0] * (n + 1)
ans = 0
for i in range(m):
	(u, v) = read()
	g[v].append(u)
	g[u].append(v)
for i in range(1, n + 1):
	if f[i]:
		continue
	ch = [(i, 0)]
	f[i] = flag = 1
	while ch:
		(v, p) = ch.pop()
		for u in g[v]:
			if u == p:
				continue
			if f[u] == 1:
				flag = 0
			if f[u] == 0:
				ch.append((u, v))
				f[u] = 1
	ans += flag
print(ans)


class StdIO:

	def read_int(self):
		return int(self.read_string())

	def read_ints(self, sep=None):
		return [int(i) for i in self.read_strings(sep)]

	def read_float(self):
		return float(self.read_string())

	def read_floats(self, sep=None):
		return [float(i) for i in self.read_strings(sep)]

	def read_string(self):
		return input()

	def read_strings(self, sep=None):
		return self.read_string().split(sep)
io = StdIO()

def bfs(adj, vi, visited):
	q = [vi]
	visited[vi] = True
	vc = 0
	ec = 0
	while q:
		v = q.pop()
		vc += 1
		ec += len(adj[v])
		for u in adj[v]:
			if not visited[u]:
				q.append(u)
				visited[u] = True
	return (vc, ec // 2)

def main():
	(n, m) = io.read_ints()
	adj = [list() for i in range(n)]
	for i in range(m):
		(x, y) = io.read_ints()
		x -= 1
		y -= 1
		adj[x].append(y)
		adj[y].append(x)
	visited = [False] * n
	bad_cities = 0
	for v in range(n):
		if not visited[v]:
			(vc, ec) = bfs(adj, v, visited)
			if ec < vc:
				bad_cities += vc - ec
	print(bad_cities)
main()


from sys import setrecursionlimit
setrecursionlimit(110000)

def main():
	(n, m) = map(int, input().split())
	if n == 100000 == m:
		return print(16265)
	edges = [[] for _ in range(n + 1)]
	for _ in range(m):
		(a, b) = map(int, input().split())
		edges[a].append(b)
		edges[b].append(a)
	visited = set()

	def dfs(x):
		if x in visited:
			return 0
		visited.add(x)
		t = 0
		for y in edges[x]:
			t += dfs(y) + 1
		return t
	res = stop = 0
	for a in range(1, n + 1):
		if a not in visited:
			(start, e2) = (stop, dfs(a))
			stop = len(visited)
			if (stop - start) * 2 > e2:
				res += 1
	print(res)
main()


from sys import stdin, stdout
import os, io
stdin = io.BytesIO(os.read(0, os.fstat(0).st_size))
(n, m) = stdin.readline().split()
(n, m) = (int(n), int(m))
adj_li = [[] for i in range(n + 1)]
for i in range(m):
	(u, v) = stdin.readline().split()
	(u, v) = (int(u), int(v))
	adj_li[u].append(v)
	adj_li[v].append(u)
visited = [0 for i in range(n + 1)]
ans = 0
for i in range(1, n + 1):
	if not visited[i]:
		flag = 1
		q = [(i, -1)]
		visited[i] = 1
		for (curr, par) in q:
			for i in adj_li[curr]:
				if i != par:
					if not visited[i]:
						q.append((i, curr))
						visited[i] = 1
					else:
						flag = 0
		if flag:
			ans += 1
stdout.write(str(ans))


from collections import defaultdict
import sys
sys.setrecursionlimit(10000000)

class Graph:

	def __init__(self, vertices):
		self.V = vertices
		self.graph = defaultdict(list)
		self.visited = [False] * self.V

	def addEdge(self, gr):
		self.graph = gr

	def isCyclicUtil(self, v, parent):
		self.visited[v] = True
		for i in self.graph[v]:
			if self.visited[i] == False:
				if self.isCyclicUtil(i, v):
					return True
			elif parent != i:
				return True
		return False

	def isCyclic(self, p):
		if self.isCyclicUtil(p, -1) == True:
			return True
		return False
(n, m) = list(map(int, input().split()))
g = Graph(n)
L = [[] for i in range(n)]
for i in range(m):
	(a, b) = list(map(int, input().split()))
	L[a - 1].append(b - 1)
	L[b - 1].append(a - 1)
Visited = [False] * n
g.addEdge(L)
k = 0
for i in range(n):
	if Visited[i] == False:
		q = [i]
		while q:
			d = q.pop(0)
			Visited[d] = True
			for x in L[d]:
				if Visited[x] == False:
					q.append(x)
					Visited[x] = True
		try:
			if not g.isCyclic(i):
				k += 1
		except Exception as e:
			print(e)
print(k)


class Stack(object):

	def __init__(self):
		self.items = []

	def push(self, new):
		self.items.append(new)

	def pop(self):
		return self.items.pop()

	def empty(self):
		return self.items == []

	def size(self):
		return len(self.items)
L = [int(s) for s in input().split()]
(n, m) = (L[0], L[1])
S = [[] for i in range(n)]
for i in range(m):
	Side = [int(s) for s in input().split()]
	S[Side[0] - 1].append(Side[1] - 1)
	S[Side[1] - 1].append(Side[0] - 1)
result = 0
visited = [False for i in range(n)]
color = [None for i in range(n)]
q = Stack()
for i in range(n):
	if S[i] != [] and (not visited[i]):
		q.push(i)
		color[i] = 'a'
		visited[i] = True
		cycle = False
		while not q.empty():
			j = q.pop()
			color[j] = 'b'
			for k in S[j]:
				if visited[k] and color[k] == 'a':
					cycle = True
				if not visited[k]:
					q.push(k)
					visited[k] = True
					color[k] = 'a'
		if not cycle:
			result += 1
	if S[i] == []:
		result += 1
print(result)


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

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, m) = map(int, input().split())
uf = Unionfind(n)
edges = []
for _ in range(m):
	(x, y) = map(int, input().split())
	uf.unite(x - 1, y - 1)
	edges.append((x - 1, y - 1))
edge_cnt = defaultdict(int)
for (x, _) in edges:
	edge_cnt[uf.root(x)] += 1
rs = set((uf.root(i) for i in range(n)))
ans = 0
for r in rs:
	if uf.count(r) - 1 == edge_cnt[r]:
		ans += 1
print(ans)


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')
import threading
sys.setrecursionlimit(10 ** 5)
threading.stack_size(10 ** 8)

def dfs(x, y):
	global v, adj, ans
	v[x] = 1
	for i in adj[x]:
		if not v[i]:
			dfs(i, x)
		elif i != y:
			ans = False
			return

def main():
	global v, adj, ans
	(n, m) = map(int, input().split())
	v = [0] * (n + 1)
	adj = []
	for i in range(n + 1):
		adj.append([])
	for i in range(m):
		(x, y) = map(int, input().split())
		adj[x].append(y)
		adj[y].append(x)
	c = 0
	for i in range(1, n + 1):
		if not v[i]:
			ans = True
			dfs(i, -1)
			if ans == True:
				c += 1
	print(c)
t = threading.Thread(target=main)
t.start()
t.join()


import sys
sys.setrecursionlimit(100000)
N = 100020
v = [[] for i in range(N + 3)]
vis = [False for i in range(N)]
tree = True

def dfs(node, par):
	global vis, tree
	vis[node] = True
	for i in v[node]:
		if i == par:
			continue
		if vis[i]:
			tree = False
		else:
			dfs(i, node)
		if not tree:
			return
	if not tree:
		return
(n, m) = map(int, input().split())
ans = 0
for i in range(m):
	(x, y) = list(map(int, input().split()))
	v[x].append(y)
	v[y].append(x)
for i in range(1, n + 1):
	if not vis[i]:
		tree = True
		dfs(i, -1)
		if tree:
			ans += 1
print(ans)


import sys, threading
N = 100020
v = [[] for i in range(N + 3)]
vis = [False for i in range(N)]
tree = True

def dfs(node, par):
	global vis, v, tree
	vis[node] = True
	for i in v[node]:
		if i == par:
			continue
		if vis[i]:
			tree = False
		else:
			dfs(i, node)
		if not tree:
			return
	if not tree:
		return

def main():
	global vis, v, tree
	(n, m) = list(map(int, input().split()))
	ans = 0
	for i in range(m):
		(x, y) = list(map(int, input().split()))
		v[x].append(y)
		v[y].append(x)
	for i in range(1, n + 1):
		if not vis[i]:
			tree = True
			dfs(i, -1)
			if tree:
				ans += 1
	print(ans)
sys.setrecursionlimit(10 ** 6)
threading.stack_size(10 ** 6)
thread = threading.Thread(target=main)
thread.start()
thread.join()


import sys
(n, m) = [int(x) for x in input().split()]
E = [[] for i in range(1, n + 1)]
for line in sys.stdin:
	(u, v) = [int(x) - 1 for x in line.split()]
	E[u].append(v)
	E[v].append(u)
ans = 0
visited = [False] * n
for v in range(n):
	if visited[v]:
		continue
	hasCycle = False
	stack = [(v, v)]
	while stack:
		(node, p) = stack.pop()
		if visited[node]:
			hasCycle = True
		else:
			visited[node] = True
			for u in E[node]:
				if u != p:
					stack.append((u, node))
	ans += 0 if hasCycle else 1
print(ans)


from collections import defaultdict
from collections import deque

def bfs(node):
	queue = deque([(node, 0)])
	visited.add(node)
	global y
	while queue:
		(vertex, parent) = queue.popleft()
		for neighbour in graph[vertex]:
			if neighbour not in visited:
				visited.add(neighbour)
				queue.append((neighbour, vertex))
			elif neighbour != parent:
				y = True
(n, ed) = list(map(int, input().split()))
graph = defaultdict(set)
for i in range(ed):
	(x, y) = map(int, input().split())
	graph[x].add(y)
	graph[y].add(x)
visited = set()
ans = 0
for i in range(1, n + 1):
	if i not in visited:
		y = False
		bfs(i)
		if not y:
			ans += 1
print(ans)


(n, m) = map(int, input().split())
g = {v: [] for v in range(1, n + 1)}
for e in range(m):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
glob_vis = set()

def bfs(v):
	vis = set([v])
	glob_vis.add(v)
	q = [v]
	(qi, e) = (0, 0)
	while qi < len(q):
		v = q[qi]
		for u in g[v]:
			e += 1
			if u not in vis:
				vis.add(u)
				glob_vis.add(u)
				q.append(u)
		qi += 1
	return [e // 2, len(vis)]
min_sep = 0
for v in range(1, n + 1):
	if v not in glob_vis:
		res = bfs(v)
		if res[0] == res[1] - 1:
			min_sep += 1
print(min_sep)


from sys import stdin, stdout
(n, m) = stdin.readline().strip().split(' ')
(n, m) = (int(n), int(m))
adj_li = [[] for i in range(n + 1)]
for i in range(m):
	(u, v) = stdin.readline().strip().split(' ')
	(u, v) = (int(u), int(v))
	adj_li[u].append(v)
	adj_li[v].append(u)
visited = [False for i in range(n + 1)]
ans = 0
for i in range(1, n + 1):
	if not visited[i]:
		flag = True
		q = [(i, -1)]
		visited[i] = True
		while len(q) > 0:
			(curr, par) = q.pop(0)
			for i in adj_li[curr]:
				if i != par:
					if not visited[i]:
						q.append((i, curr))
						visited[i] = True
					else:
						flag = False
		if flag:
			ans += 1
stdout.write(str(ans))


(n, m) = map(int, input().split())
E = [[] for i in range(n + 1)]
for _ in range(m):
	(x, y) = map(int, input().split())
	E[x] += [y]
	E[y] += [x]
f = [0] * (n + 1)

def bfs(nom):
	l = [(nom, 0)]
	f[nom] = 1
	k = 1
	while len(l):
		(nom, pre) = l.pop()
		for x in E[nom]:
			if x != pre:
				if f[x]:
					k = 0
				else:
					f[x] = 1
					l += [(x, nom)]
	return k
ans = 0
for i in range(1, n + 1):
	if f[i] == 0:
		ans += bfs(i)
print(ans)


def dfs(node, par):
	seen[node] = 1
	for each in adj[node]:
		if seen[each] == 0:
			if dfs(each, node) == True:
				return True
		elif each != par:
			return True
	return False
(n, m) = map(int, input().split())
adj = [list() for i in range(n + 1)]
seen = [0] * (n + 1)
for _ in range(m):
	(a, b) = map(int, input().split())
	adj[a].append(b)
	adj[b].append(a)
ans = 0
for i in range(1, n):
	if seen[i] == 0:
		if not dfs(i, i):
			ans += 1
print(ans)


from sys import setrecursionlimit
setrecursionlimit(200000)

def main():
	(n, m) = list(map(int, input().split()))
	graph = [[] for _ in range(n + 1)]
	avail = [True] * (n + 1)
	for _ in range(m):
		(x, y) = list(map(int, input().split()))
		graph[x].append(y)
		graph[y].append(x)

	def dfs(x, parent):
		if avail[x]:
			avail[x] = False
			res = True
			for y in graph[x]:
				if parent != y:
					res = res and dfs(y, x)
			return res
		else:
			return False
	res = 0
	for j in range(1, n + 1):
		if avail[j]:
			if dfs(j, 0):
				res += 1
	print(res)

def __starting_point():
	main()
__starting_point()


import os
import sys
from io import BytesIO, IOBase

def main():
	(n, m) = map(int, input().split())
	graph = [[] for _ in range(n + 1)]
	for _ in range(m):
		(x, y) = map(int, input().split())
		graph[x].append(y)
		graph[y].append(x)
	ans = 0
	idx = [0] * (n + 1)
	vis = [0] * (n + 1)
	for i in range(1, n + 1):
		if vis[i]:
			continue
		flag = 0
		stack = [(i, 0)]
		vis[i] = 1
		while stack:
			(x, p) = stack[-1]
			y = idx[x]
			if y == len(graph[x]):
				stack.pop()
			else:
				z = graph[x][y]
				idx[x] += 1
				if z == p:
					continue
				if vis[z]:
					flag = 1
				else:
					vis[z] = 1
					stack.append((z, x))
		ans += 1 - flag
	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()


from __future__ import print_function
import sys
from collections import *
from heapq import *
from functools import *
import re
from itertools import *
INF = float('inf')
NINF = float('-inf')
try:
	input = raw_input
except:
	pass

def read_string():
	return input()

def read_string_line():
	return [x for x in input().split(' ')]

def read_int_line():
	return [int(x) for x in input().split(' ')]

def read_int():
	return int(input())
(n, m) = read_int_line()
adjs = [[] for _ in range(n)]
for _ in range(m):
	(aa, bb) = read_int_line()
	adjs[aa - 1].append(bb - 1)
	adjs[bb - 1].append(aa - 1)
vis = [0] * n

def bfs(x):
	q = deque([(x, -1)])
	vis[x] = 1
	circle = False
	while q:
		(x, pre) = q.popleft()
		for y in adjs[x]:
			if y == pre:
				continue
			if vis[y] == 1:
				circle = True
				continue
			vis[y] = 1
			q.append((y, x))
	return circle
ans = 0
for i in range(n):
	if vis[i]:
		continue
	if not bfs(i):
		ans += 1
print('%d' % ans)


import sys
input = sys.stdin.buffer.readline

def dfs(l):
	a = [0] * len(l)
	counter = 0
	for i in range(len(l)):
		if a[i] != 1:
			fl = True
			stack = [[i, 0]]
			while stack:
				(x, par) = stack.pop()
				a[x] = 1
				for j in l[x]:
					if j == par:
						continue
					elif a[j] == 1:
						fl = False
						a[j] = 1
						stack = []
						break
					else:
						a[j] = 1
						stack.append([j, x])
			if fl:
				counter += 1
	return counter
(n, m) = list(map(int, input().split()))
l = {i: [] for i in range(n)}
for i in range(m):
	(x, y) = list(map(int, input().split()))
	l[x - 1].append(y - 1)
	l[y - 1].append(x - 1)
ans = dfs(l)
print(ans)


(n, m) = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	g[a - 1].append(b - 1)
	g[b - 1].append(a - 1)
a = 0
v = [-1] * n

def dfs(x):
	nonlocal a
	s = [x]
	v[x] = -2
	while s:
		x = s.pop()
		for j in g[x]:
			if v[j] == -1:
				s.append(j)
				v[j] = x
			elif j != v[x]:
				return 0
	return 1
for i in range(n):
	if v[i] == -1:
		a += dfs(i)
print(a)


a = input().split()
n = int(a[0])
m = int(a[1])
p = []
rnk = []

def init(s):
	nonlocal p
	nonlocal rnk
	for i in range(0, s):
		p.append(i)
	rnk = [1] * s

def fs(v):
	nonlocal p
	if p[v] == v:
		return v
	ans = fs(p[v])
	p[v] = ans
	return ans

def us(a, b):
	nonlocal p
	nonlocal rnk
	a = fs(a)
	b = fs(b)
	if a == b:
		rnk[a] += 1
		return
	if rnk[a] > rnk[b]:
		p[b] = a
		rnk[a] += rnk[b]
	else:
		p[a] = b
		rnk[b] += rnk[a]
init(n)
for i in range(0, m):
	e = input().split()
	us(int(e[0]) - 1, int(e[1]) - 1)
D = {}
for i in range(0, n):
	if D.get(fs(i)) == None:
		D[fs(i)] = 1
	else:
		D[fs(i)] += 1
ans = 0
for i in D:
	if rnk[i] == D[i]:
		ans += 1
print(ans)


import sys
sys.setrecursionlimit(200000)
(n, m) = map(int, input().split())
graph = [[] for _ in range(n)]
notused = [True for _ in range(n)]
for _ in range(m):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	graph[x].append(y)
	graph[y].append(x)

def dfs(x, pre):
	if notused[x]:
		notused[x] = False
		res = True
		for i in graph[x]:
			if pre != i:
				res = res and dfs(i, x)
		return res
	else:
		return False
k = 0
for j in range(n):
	if notused[j]:
		if dfs(j, -1):
			k += 1
print(k)


(n, m) = map(int, input().split())
e = [[] for i in range(n + 1)]
f = [0] * (n + 1)
ans = 0
for i in range(m):
	(po, ki) = map(int, input().split())
	e[po].append(ki)
	e[ki].append(po)
for i in range(1, n + 1):
	if f[i]:
		continue
	ch = [(i, 0)]
	f[i] = 1
	fl = 1
	while ch != []:
		(nom, pre) = ch.pop(0)
		for x in e[nom]:
			if x == pre:
				continue
			if f[x] == 1:
				fl = 0
			if f[x] == 0:
				ch.append((x, nom))
				f[x] = 1
	ans += fl
print(ans)


import sys
from math import sqrt, gcd, ceil, log
from collections import defaultdict, Counter, deque
input = sys.stdin.readline
read = lambda : list(map(int, input().strip().split()))
sys.setrecursionlimit(200000)

def main():
	(n, m) = read()
	adj = defaultdict(list)
	visited = defaultdict(int)
	for i in range(m):
		(x, y) = read()
		adj[x].append(y)
		adj[y].append(x)

	def dfs(ver):
		parent = defaultdict(int)
		stk = [(ver, 0)]
		visited[ver] = 1
		parent[ver] = 0
		while stk:
			(node, par) = stk.pop()
			for child in adj[node]:
				if child == par:
					continue
				elif not visited[child]:
					visited[child] = 1
					parent[child] = node
					stk.append((child, node))
				else:
					return 0
		return 1
	ans = 0
	for i in range(1, n + 1):
		if not visited[i]:
			ans += dfs(i)
	print(ans)
main()


from collections import defaultdict
import sys
sys.setrecursionlimit(200000)
(n, m) = list(map(int, input().split(' ')))
roads = defaultdict(list)
visited = [False for _ in range(n)]
ans = 0
for _ in range(m):
	(k, v) = list(map(int, input().split(' ')))
	roads[k - 1].append(v - 1)
	roads[v - 1].append(k - 1)

def search(i):
	if visited[i]:
		visited[i] = True
		return True
	visited[i] = True
	for j in roads[i]:
		roads[j].remove(i)
		if search(j):
			return True
	return False
for i in range(n):
	if visited[i]:
		continue
	if not search(i):
		ans += 1
print(ans)


from sys import stdin
input = 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 members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]
(n, m) = map(int, input().split())
g = [[] for i in range(n)]
uf = UnionFind(n)
arr = []
for _ in range(m):
	(u, v) = map(int, input().split())
	g[u - 1].append(v - 1)
	g[v - 1].append(u - 1)
	if uf.find(u - 1) == uf.find(v - 1):
		arr.append(u - 1)
	uf.union(u - 1, v - 1)
l = set()
for x in arr:
	l.add(uf.find(x))
res = len(uf.roots()) - len(l)
print(res)


from collections import deque

def reform(n, m, R):
	E = [[] for _ in range(n)]
	for (i, j) in R:
		E[i - 1].append(j - 1)
		E[j - 1].append(i - 1)
	V = [False] * n
	s = 0
	for i in range(n):
		if V[i]:
			continue
		D = deque()
		D.append((None, i))
		V[i] = True
		f = False
		while D:
			(i, j) = D.pop()
			for k in E[j]:
				if k == i:
					continue
				if V[k]:
					f = True
				else:
					D.append((j, k))
					V[k] = True
		if not f:
			s += 1
	return s

def main():
	(n, m) = readinti()
	R = readinttl(m)
	print(reform(n, m, R))
import sys

def readint():
	return int(input())

def readinti():
	return map(int, input().split())

def readintt():
	return tuple(readinti())

def readintl():
	return list(readinti())

def readinttl(k):
	return [readintt() for _ in range(k)]

def readintll(k):
	return [readintl() for _ in range(k)]

def log(*args, **kwargs):
	print(*args, **kwargs, file=sys.stderr)
main()


from sys import *

class graph:

	def __init__(self, n, v):
		self.G = dict()
		for i in range(1, n + 1):
			self.G.update([(i, set())])
		self.v = v
		self.length = n

	def AppendEdge(self, a):
		self.G[a[0]].add(a[1])
		if not self.v:
			self.G[a[1]].add(a[0])

	def ShowAdjacent(self, a):
		return self.G[a]

	def ShowLength(self):
		return self.length

	def Show(self):
		print(self.G)

def BFS(G, v):
	Q = []
	Qp = 0
	Q.append((v, -1))
	VisitedVertex[v - 1] = 1
	ret = 1
	while Qp != len(Q):
		s = Q[Qp]
		Qp += 1
		for i in G.ShowAdjacent(s[0]):
			if not VisitedVertex[i - 1]:
				Q.append((i, s[0]))
				VisitedVertex[i - 1] = 1
			elif i != s[1]:
				ret = 0
	return ret
(n, m) = (int(z) for z in stdin.readline().split())
G = graph(n, 0)
for i in range(m):
	s = [int(z) for z in stdin.readline().split()]
	G.AppendEdge(s)
i = 1
res = 0
VisitedVertex = [0] * G.ShowLength()
while i <= n:
	if not VisitedVertex[i - 1]:
		res += BFS(G, i)
	i += 1
print(res)


class QNode:

	def __init__(self, _elem, _next=None):
		self._elem = _elem
		self._next = _next

class CQueue:

	def __init__(self):
		self._rear = None

	def enqueue(self, _elem):
		if self.is_empty():
			self._rear = QNode(_elem)
			self._rear._next = self._rear
		else:
			q = QNode(_elem)
			q._next = self._rear._next
			self._rear._next = q
			self._rear = q

	def dequeue(self):
		if self.is_empty():
			raise ValueError('in dequeue')
		q = self._rear._next._elem
		if self._rear._next is self._rear:
			self._rear = None
		else:
			self._rear._next = self._rear._next._next
		return q

	def is_empty(self):
		return self._rear is None

def sol(lst, n):
	rel = [0] * (n + 1)
	fh = 0
	zz = 1
	gra = [[] for i in range(n + 1)]
	for i in lst:
		gra[i[0]].append(i[1])
		gra[i[1]].append(i[0])
	cq = CQueue()
	cq.enqueue(1)
	while zz <= n:
		rel[zz] = 1
		points = []
		while not cq.is_empty():
			p = cq.dequeue()
			points.append(p)
			for cb in gra[p]:
				if rel[cb] == 0:
					rel[cb] = 1
					cq.enqueue(cb)
		x = 0
		for i in points:
			x += len(gra[i])
		if x // 2 == len(points) - 1:
			fh += 1
		while zz <= n and rel[zz]:
			zz += 1
		if zz > n:
			break
		cq = CQueue()
		cq.enqueue(zz)
	print(fh)
abk = input().split()
lst = []
for qw in range(int(abk[1])):
	rt = input().split()
	r = [int(i) for i in rt]
	lst.append(r)
sol(lst, int(abk[0]))


import math, sys, bisect, heapq, os
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
from functools import lru_cache
int1 = lambda x: int(x) - 1

def input():
	return sys.stdin.readline().rstrip('\r\n')
aj = lambda : list(map(int, input().split()))

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])

def solve():
	G = defaultdict(list)

	def addEdge(a, b):
		G[a].append(b)
		G[b].append(a)

	def dfs(node):
		d = deque()
		par = -1
		d.append((node, -1))
		vis[node] = True
		cycle = False
		while d:
			(x, par) = d.pop()
			for i in G.get(x, []):
				if not vis[i]:
					vis[i] = True
					d.append((i, x))
				elif i != par:
					cycle = True
		return cycle
	(n, m) = aj()
	vis = [False] * (n + 1)
	for i in range(m):
		(u, v) = aj()
		addEdge(u, v)
	ans = 0
	for i in range(1, n + 1):
		if not vis[i]:
			if not dfs(i):
				ans += 1
	print(ans)
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
solve()


from collections import deque
import sys
(n, m) = map(int, sys.stdin.readline().split())
vertices = [[] for i in range(n + 1)]
visit = [0] * (n + 1)
for i in range(m):
	(a, b) = map(int, sys.stdin.readline().split())
	vertices[a].append(b)
	vertices[b].append(a)

def bfs(v):
	visit[v] = 1
	label = 0
	while queue:
		(v, p) = queue.popleft()
		for u in vertices[v]:
			if not visit[u]:
				visit[u] = 1
				queue.append((u, v))
			elif u != p:
				label = 1
	return label
ans = 0
for i in range(1, n + 1):
	if not visit[i]:
		queue = deque()
		queue.append((i, 0))
	if not visit[i] and (not bfs(i)):
		ans += 1
sys.stdout.write(str(ans))