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: interview

Starter code:

Solutions:
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)



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)
    

    


3

# from collections import deque

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 = deque()
	# q.append(vi)
	q = [vi]
	visited[vi] = True

	vc = 0
	ec = 0

	while q:
		# v = q.popleft()
		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 dfs(adj, v, visited):
# 	visited[v] = True

# 	for u in adj[v]:
# 		if not visited[u]:
# 			dfs(adj, u, visited)


def main():
	n, m = io.read_ints()
	# n = 100001
	# m = 100000

	adj = [list() for i in range(n)]

	for i in range(m):
		x, y = io.read_ints()
		# x, y = i+1, i+2
		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)


def __starting_point():
	main()

__starting_point()

import sys

sys.setrecursionlimit(200000)

n, m = list(map(int, input().split()))

graph = [[] for _ in range(n)]
notused = [True for _ in range(n)]

for _ in range(m):
    x, y = list(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)


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)


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)

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()
    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)

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))

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)

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)


read = lambda: list(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)


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()

from sys import setrecursionlimit

setrecursionlimit(200000)


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)


def __starting_point():
    main()

__starting_point()

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)


def __starting_point():
    main()

__starting_point()

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)

# this is a copy from http://codeforces.com/blog/entry/59832
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)

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)

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)

from collections import defaultdict 
import sys
sys.setrecursionlimit(10000000)
#This class represents a undirected graph using adjacency list representation 
class Graph: 
   
    def __init__(self,vertices): 
        self.V= vertices #No. of vertices 
        self.graph = defaultdict(list) # default dictionary to store graph 
        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
           
   
    #Returns true if the graph contains a cycle, else 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)
        
  


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:
			#print(q)
			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;
						#adj[i].remove(curr)
					else:
						#print("flag false",curr,i)
						flag=False
		if flag:
			ans+=1
stdout.write(str(ans))

from sys import stdin,stdout
# Testing https://codeforces.com/contest/659/submission/54795830

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
		for curr,par in q:
			for i in adj_li[curr]:
				if i!=par:
					if not visited[i]:
						q.append((i,curr));
						visited[i]=True;
						#adj[i].remove(curr)
					else:
						#print("flag false",curr,i)
						flag=False
		if flag:
			ans+=1
stdout.write(str(ans))

from sys import stdin,stdout
# Testing https://codeforces.com/contest/659/submission/54795830

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
		for curr,par in q:
			for i in adj_li[curr]:
				if i!=par:
					if not visited[i]:
						q.append((i,curr));
						visited[i]=True;
						#adj[i].remove(curr)
					else:
						#print("flag false",curr,i)
						flag=False
		if flag:
			ans+=1
stdout.write(str(ans))

from sys import stdin,stdout
# Testing https://codeforces.com/contest/659/submission/54795830

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=[(2,3), (i,-1)];visited[i]=True
		while len(q) > 1:
			curr,par = q.pop()
			for i in adj_li[curr]:
				if i!=par:
					if not visited[i]:
						q.append((i,curr));
						visited[i]=True;
						#adj[i].remove(curr)
					else:
						#print("flag false",curr,i)
						flag=False
		if flag:
			ans+=1
stdout.write(str(ans))

from sys import stdin,stdout
# Testing https://codeforces.com/contest/659/submission/54795830

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=[(2,3), (i,-1)];visited[i]=True
		while len(q) > 1:
			curr,par = q.pop(1)
			for i in adj_li[curr]:
				if i!=par:
					if not visited[i]:
						q.append((i,curr));
						visited[i]=True;
						#adj[i].remove(curr)
					else:
						#print("flag false",curr,i)
						flag=False
		if flag:
			ans+=1
stdout.write(str(ans))