You are given a tree (a simple connected graph with no cycles). 

Find the maximum number of edges you can remove from the tree to get a forest such that each connected component of the forest contains an even number of nodes.

As an example, the following tree with $4$ nodes can be cut at most $1$ time to create an even forest.  

Function Description  

Complete the evenForest function in the editor below.  It should return an integer as described.  

evenForest has the following parameter(s):  

t_nodes: the number of nodes in the tree  
t_edges: the number of undirected edges in the tree  
t_from: start nodes for each edge  
t_to: end nodes for each edge, (Match by index to t_from.)  

Input Format

The first line of input contains two integers $t_{n}odes$ and $t_e dges$, the number of nodes and edges. 

The next $t_e dges$ lines contain two integers $t_{f}rom[i]$ and $t_to[i]$ which specify nodes connected by an edge of the tree. The root of the tree is node $1$.

Constraints

$2\leq n\leq100$ 
$n\in\mathbb{Z}^+_{\text{even}}$  

Note: The tree in the input will be such that it can always be decomposed into components containing an even number of nodes. $\mathbb{Z}_{\text{even}}^{+}$ is the set of positive even integers.

Output Format

Print the number of removed edges.

Sample Input 1

10 9
2 1
3 1
4 3
5 2
6 1
7 2
8 6
9 8
10 8

Sample Output 1

2

Explanation 1

Remove edges ${(1,3)}$  and ${(1,6)}$ to get the desired result.

No more edges can be removed.

Source: hackerrank | Difficulty: MEDIUM
Tags: Graph algorithms


Solutions:
__author__ = 'Ahn'
(N, M) = input().split()
N = int(N)
M = int(M)
child = {}
tree = {}
for i in range(1, M + 1):
	(ui, vi) = input().split()
	ui = int(ui)
	vi = int(vi)
	if vi not in tree.keys():
		tree[vi] = [ui]
	else:
		tree[vi].append(ui)
	child[i] = 1
for i in range(M + 1, 1, -1):
	if i not in tree.keys():
		child[i] = 1
	else:
		for j in tree[i]:
			child[i] = child[i] + child[j]
count = 0
for i in range(1, M + 1):
	if child[i] % 2 == 0:
		count += 1
print(count)


from collections import defaultdict

class Node:
	__slots__ = ['children', 'size', 'inited']

	def __init__(self):
		self.children = []
		self.inited = False
		self.size = -1

def calcSize(d, k):
	node = d[k]
	if node.inited:
		return node.size
	node.inited = True
	size = 0
	for c in node.children:
		size += calcSize(d, c)
	node.size = 1 + size
	return node.size

def main():
	(V, E) = list(map(int, input().split()))
	d = defaultdict(Node)
	for i in range(E):
		(target, source) = list(map(int, input().split()))
		d[source].children.append(target)
	keys = d.keys()
	for k in sorted(keys, reverse=True):
		calcSize(d, k)
	s = 0
	for k in sorted(keys):
		for c in d[k].children:
			if d[c].size % 2 == 0:
				s += 1
	print(s)
main()


def setNodeCounts(nodes, index=0, open_nodes=[]):
	if nodes[index]['count'] != 0:
		return nodes[index]['count']
	count = 1
	open_nodes.append(index)
	nodes[index]['count'] = count
	for node_idx in nodes[index]['adjacent']:
		if node_idx not in open_nodes:
			count += setNodeCounts(nodes, node_idx, open_nodes)
	nodes[index]['count'] = count
	return nodes[index]['count']

def main():
	raw_string = input().split(' ')
	v_count = int(raw_string[0])
	e_count = int(raw_string[1])
	nodes = [{'adjacent': [], 'count': 0} for i in range(v_count)]
	for i in range(e_count):
		raw_edge = input().split(' ')
		(x, y) = (int(raw_edge[0]) - 1, int(raw_edge[1]) - 1)
		nodes[x]['adjacent'].append(y)
		nodes[y]['adjacent'].append(x)
	setNodeCounts(nodes)
	count = 0
	for node in nodes:
		if node['count'] % 2 == 0:
			count += 1
	print(count - 1)
main()


def evenTree(e):
	if len(e) <= 2:
		return 0
	for i in e:
		if len(e[i]) == 1:
			continue
		for j in e[i]:
			s = [i]
			visited = {j}
			count = 0
			edges = {}
			while len(s) > 0:
				curr = s.pop(-1)
				for k in e[curr]:
					if k not in visited:
						s.append(k)
						count += 1
						visited.add(k)
						if curr not in edges:
							edges[curr] = [k]
						elif k not in edges[curr]:
							edges[curr].append(k)
						if k not in edges:
							edges[k] = [curr]
						elif curr not in edges[k]:
							edges[k].append(curr)
			if count > 0 and count % 2 == 0:
				s = [j]
				visited = {i}
				edges2 = {}
				while len(s) > 0:
					curr = s.pop(-1)
					for k in e[curr]:
						if k not in visited:
							s.append(k)
							visited.add(k)
							if curr not in edges2:
								edges2[curr] = [k]
							elif k not in edges2[curr]:
								edges2[curr].append(k)
							if k not in edges2:
								edges2[k] = [curr]
							elif curr not in edges2[k]:
								edges2[k].append(curr)
				return 1 + evenTree(edges) + evenTree(edges2)
	return 0
(n, m) = [int(i) for i in input().split()]
es = {}
for i in range(m):
	(a, b) = [int(j) for j in input().split()]
	if a not in es:
		es[a] = [b]
	else:
		es[a].append(b)
	if b not in es:
		es[b] = [a]
	else:
		es[b].append(a)
print(evenTree(es))


theInfo = list(map(int, input().split(' ')))
theGraph = [0] * (theInfo[0] + 1)
for i in range(theInfo[0] + 1):
	theGraph[i] = {'val': i, 'parent': None, 'children': [], 'size': 0}
for i in range(theInfo[1]):
	myInput = list(map(int, input().split(' ')))
	theGraph[myInput[0]]['parent'] = myInput[1]
	theGraph[myInput[1]]['children'].append(myInput[0])
theCount = {'x': -1}

def markSize(aNode):
	if len(aNode['children']) == 0:
		aNode['size'] = 1
		return 1
	else:
		mySize = 1
		for aChild in aNode['children']:
			mySize = mySize + markSize(theGraph[aChild])
		aNode['size'] = mySize
		if mySize % 2 == 0:
			theCount['x'] = theCount['x'] + 1
		return mySize
markSize(theGraph[1])
print(theCount['x'])


import sys

def evenTree(root, edges):
	if len(edges[root]) == 0:
		return (0, False)
	odd = 0
	removed = 0
	for i in edges[root]:
		result = evenTree(i, edges)
		removed = removed + result[0]
		if result[1]:
			removed = removed + 1
		else:
			odd = odd + 1
	return (removed, odd % 2 == 1)
line = sys.stdin.readline().split(' ')
n = int(line[0])
m = int(line[1])
edges = [[] for i in range(n)]
for i in range(m):
	line = sys.stdin.readline().split(' ')
	x = int(line[0])
	y = int(line[1])
	edges[y - 1].append(x - 1)
result = evenTree(0, edges)
sys.stdout.write(str(result[0]))


def subTreeSize(currVal, children):
	if children[currVal] == []:
		return {currVal: 1}
	else:
		treeSize = 1
		output = {}
		for child in children[currVal]:
			childSize = subTreeSize(child, children)
			output.update(childSize)
			treeSize += output[child]
		output[currVal] = treeSize
		return output
(n, m) = [int(val) for val in input().split()]
children = {key: [] for key in list(range(1, n + 1))}
for i in range(m):
	(child, parent) = [int(val) for val in input().split()]
	children[parent].append(child)
subSize = subTreeSize(1, children)
sizes = subSize.values()
output = 0
for e in sizes:
	if e % 2 == 0:
		output += 1
print(output - 1)


(N, M) = [int(x) for x in input().split(' ')]
tree = [set() for _ in range(0, N)]
for m in range(0, M):
	(a, b) = [int(x) for x in input().split(' ')]
	if a > b:
		(a, b) = (b, a)
	tree[a - 1].add(b - 1)
treeSize = [0] * N
count = 0
for n in range(N - 1, -1, -1):
	s = 1
	for e in tree[n]:
		s += treeSize[e]
	treeSize[n] = s
	if s % 2 == 0:
		count += 1
print(count - 1)


class Tree:

	def __init__(self, value=None):
		self.size = value
		self.children = list()

	def __iter__(self):
		for child in self.children:
			yield child

	def add_child(self, node):
		self.children.append(node)

	def set_to_count(self):
		self.value = 1 + sum((child.set_to_count() for child in self))
		return self.value

	def even_subtrees(self):
		evens = 0
		for child in self:
			if child.value % 2 == 0:
				evens += 1
			evens += child.even_subtrees()
		return evens
(nV, nE) = map(int, input().strip().split())
edges = list()
for n in range(nE):
	edges.append(tuple(map(int, input().strip().split())))
nodes = [Tree() for n in range(nV)]
for (c, p) in edges:
	nodes[p - 1].add_child(nodes[c - 1])
tree = nodes[0]
tree.set_to_count()
print(tree.even_subtrees())


def subtree_sizes(edges):

	def helper(nodeID, edges, subtreeSizes):
		if nodeID not in edges:
			subtreeSizes[nodeID] = 1
		else:
			subtreeSize = 0
			for childID in edges[nodeID]:
				helper(childID, edges, subtreeSizes)
				subtreeSize += subtreeSizes[childID]
			subtreeSizes[nodeID] = 1 + subtreeSize
	subtreeSizes = dict()
	helper(1, edges, subtreeSizes)
	return subtreeSizes

def num_edges_removed(edges, subtreeSizes):
	numRemoved = 0
	nodeStack = [1]
	while len(nodeStack) > 0:
		nodeID = nodeStack.pop()
		if nodeID not in edges:
			continue
		else:
			for childID in edges[nodeID]:
				if subtreeSizes[childID] & 1 == 0:
					numRemoved += 1
				nodeStack.append(childID)
	return numRemoved

def main():
	(n, m) = (int(i) for i in input().split())
	edges = {}
	for _ in range(m):
		(root, leaf) = sorted((int(i) for i in input().split()))
		if root not in edges:
			edges[root] = [leaf]
		else:
			edges[root].append(leaf)
	subtrees = subtree_sizes(edges)
	print(num_edges_removed(edges, subtrees))
main()


import sys
import collections

class Node:

	def __init__(self):
		self.children = set()
		self.weight = 1

	def __str__(self):
		return 'children: {}, weight: {}'.format(self.children, self.weight)

def dfs(node, graph):
	for child in graph[node].children:
		if graph[child].weight == 1 and graph[child].children:
			dfs(child, graph)
	graph[node].weight += sum([graph[child].weight for child in graph[node].children])

def solve(node, graph, edges_to_remove):
	for child in graph[node].children:
		if graph[child].weight % 2 == 0:
			edges_to_remove.add((node, child))
		solve(child, graph, edges_to_remove)
[_, M] = [int(X) for X in sys.stdin.readline().split()]
graph = collections.defaultdict(Node)
for edge in range(M):
	[child, parent] = [int(X) for X in sys.stdin.readline().split()]
	graph[parent].children.add(child)
dfs(1, graph)
edges_to_remove = set()
solve(1, graph, edges_to_remove)
print(len(edges_to_remove))


(N, M) = [int(i) for i in str(input()).split()]
c = [1 for i in range(N)]
edges = []
for i in range(M):
	edges.append([int(i) - 1 for i in str(input()).split()])
edges.reverse()
for edge in edges:
	c[edge[1]] += c[edge[0]]
ret = -1 if max(c) % 2 == 0 else 0
for v in c:
	if v % 2 == 0:
		ret += 1
print(ret)


class Node:

	def __init__(self, name):
		self.edges = []
		self.name = name

	def __str__(self):
		return '%d: [%s]' % (self.name, ' '.join([str(e.name) for e in self.edges]))

	def visit(self, path, neighbors):
		path[self.name] = 0
		myNeighbors = [self.name]
		forests = 0
		for e in self.edges:
			if e.name not in path:
				forests += e.visit(path, myNeighbors)
		if len(myNeighbors) % 2 == 0:
			forests += 1
		else:
			neighbors += myNeighbors
		return forests

def search(nodes):
	firstNode = nodes[list(nodes.keys())[0]]
	path = {}
	neighbors = []
	return firstNode.visit(path, neighbors) - 1
(n, m) = list(map(int, input().strip().split(' ')))
nodes = {}
for i in range(m):
	(a, b) = list(map(int, input().strip().split(' ')))
	for nodeName in (a, b):
		if nodeName not in nodes:
			nodes[nodeName] = Node(nodeName)
	nodes[a].edges.append(nodes[b])
	nodes[b].edges.append(nodes[a])
print(search(nodes))


(N, M) = [int(x) for x in input().split(' ')]
edges = dict()
edges_list = []
for i in range(M):
	(a, b) = [int(x) for x in input().split(' ')]
	edges[a] = edges.get(a, set()).union([b])
	edges[b] = edges.get(b, set()).union([a])
	edges_list.append([a, b])
import queue
done = False
removed_count = 0

def get_weight(n_child, n_parent):
	q = queue.Queue()
	q.put(n_child)
	nodes = set()
	while not q.empty():
		pos = q.get()
		nodes.add(pos)
		for pos_n in edges.get(pos, set()):
			if pos_n == n_parent:
				continue
			if pos_n in nodes:
				continue
			q.put(pos_n)
	return len(nodes)
for (a, b) in edges_list:
	if get_weight(a, b) % 2 == 0 and get_weight(b, a) % 2 == 0:
		edges[a].remove(b)
		edges[b].remove(a)
		removed_count += 1
print(removed_count)


class TreeNode:

	def __init__(self):
		self.value = 1
		self.children = []

def getHeader():
	[n, m] = [int(x) for x in input().split()[0:2]]
	return (n, m)

def getNodes(n):
	return [TreeNode() for _ in range(0, n)]

def getEdges(m):
	for i in range(0, m):
		[a, b] = [int(x) for x in input().split()[0:2]]
		yield (a, b)

def makeTree(nodes, edges):
	for (a, b) in edges:
		nodes[b - 1].children.append(nodes[a - 1])
	return nodes[0]

def postOrderTraversal(tree):
	totalCount = 1
	totalRemovals = 0
	for node in tree.children:
		(count, removals) = postOrderTraversal(node)
		totalCount += count
		totalRemovals += removals
	if totalCount > 0 and totalCount % 2 == 0:
		totalCount = 0
		totalRemovals += 1
	return (totalCount, totalRemovals)
(n, m) = getHeader()
tree = makeTree(getNodes(n), getEdges(m))
(_, out) = postOrderTraversal(tree)
print(out - 1)


(n_nodes, n_edges) = [int(x) for x in input().split()]
g = dict()
for i in range(n_edges):
	(a, b) = [int(x) for x in input().split()]
	if a in g:
		g[a].append(b)
	else:
		g[a] = [b]
	if b in g:
		g[b].append(a)
	else:
		g[b] = [a]
marked = set()

def recurse(node):
	(typ, num) = ('ODD', 0)
	marked.add(node)
	for i in g[node]:
		if i in marked:
			continue
		(typ_c, num_c) = recurse(i)
		if typ_c == 'ODD' and typ == 'EVEN':
			typ = 'ODD'
		elif typ_c == 'ODD' and typ == 'ODD':
			typ = 'EVEN'
		if typ_c == 'EVEN':
			num += num_c + 1
		else:
			num += num_c
	return (typ, num)
(_, num) = recurse(1)
print(num)


from collections import deque

def subgraph(graph, start_vertex):
	stack = deque()
	discovered = set()
	stack.append(start_vertex)
	while stack:
		vertex = stack.pop()
		if vertex not in discovered:
			discovered.add(vertex)
			for adjacent_vertex in graph.get(vertex, []):
				stack.append(adjacent_vertex)
	return discovered
line = input('').split()
(N, M) = (int(line[0]), int(line[1]))
graph = {}
for __ in range(M):
	line = input('').split()
	(u, v) = (int(line[0]), int(line[1]))
	if v not in graph:
		graph[v] = []
	graph[v].append(u)
answer = 0
for start_vertex in graph.keys():
	if start_vertex == 1:
		continue
	if len(subgraph(graph, start_vertex)) % 2 == 0:
		answer += 1
print(answer)


import sys
import queue

def readInputs0():
	global n, lAdj, lCost
	(n, _) = map(int, input().split())
	lAdj = [[] for _ in range(n)]
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		lAdj[a] += [b]
		lAdj[b] += [a]

def readInputs():
	global n, lAdj, lCost
	(n, _) = map(int, input().split())
	lAdj = [[] for _ in range(n)]
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		lAdj[a - 1] += [b - 1]
		lAdj[b - 1] += [a - 1]

def DFexplo():
	global listFather, listChildren
	listFather = n * [-1]
	listChildren = [set() for _ in range(n)]
	lifo = [0]
	while len(lifo) > 0:
		node = lifo.pop()
		for child in lAdj[node]:
			if child != listFather[node]:
				listFather[child] = node
				listChildren[node] |= {child}
				lifo.append(child)

def BFexplo():
	global nodesBF
	nodesBF = []
	fifo = queue.deque()
	fifo.append(0)
	while len(fifo) > 0:
		node = fifo.pop()
		for child in listChildren[node]:
			fifo.append(child)
			nodesBF += [child]

def propagateTotalCostsToRoots():
	global listNbNodes
	listNbNodes = n * [1]
	for node in reversed(nodesBF):
		listNbNodes[listFather[node]] += listNbNodes[node]

def solve():
	lifo = [0]
	count = 0
	while len(lifo) > 0:
		node = lifo.pop()
		for child in listChildren[node]:
			lifo.append(child)
			nbNodes = listNbNodes[child]
			if nbNodes % 2 == 0:
				count += 1
	return count
readInputs()
DFexplo()
BFexplo()
propagateTotalCostsToRoots()
print(solve())


def sort_trees(trees):
	ret = [[trees[0][0], trees[0][1]]]
	for tup in trees[1:]:
		condition = False
		for tree in ret:
			if tup[0] in tree:
				tree.append(tup[1])
				condition = True
			elif tup[1] in tree:
				tree.append(tup[0])
				condition = True
		if condition == False:
			ret.append([tup[0], tup[1]])
	condition = True
	for i in ret:
		if len(i) % 2 != 0:
			condition = False
	return condition
tree = []
(vertices, edges) = map(int, input().split(' '))
no_removed_edges = 0
for i in range(edges):
	tree.append(tuple(map(int, input().split(' '))))
for i in range(len(tree)):
	new_tree = list(tree)
	new_tree.pop(i)
	if sort_trees(new_tree) == True:
		no_removed_edges += 1
print(no_removed_edges)


def calculate_removed_edges(graph):
	children_count = {}
	visited = set()
	stack = [1]
	while stack:
		current = stack[-1]
		visited.add(current)
		for edge in graph[current]:
			if edge not in visited:
				stack.append(edge)
				break
		else:
			result = 1
			for edge in graph[current]:
				if edge in children_count:
					result += children_count[edge]
			children_count[current] = result
			stack.pop()
	return len([i for i in filter(lambda x: x[1] % 2 == 0, children_count.items())]) - 1

def main():
	graph = {}
	(n, m) = [int(i) for i in input().split()]
	for i in range(n):
		graph[i + 1] = []
	for i in range(1, m + 1):
		(left, right) = [int(i) for i in input().split()]
		graph[left].append(right)
		graph[right].append(left)
	print(calculate_removed_edges(graph))
main()


from collections import defaultdict

def nodecount(root, rootgraph):
	count = 1
	frontier = [root]
	while frontier:
		u = frontier.pop()
		for v in rootgraph[u]:
			count += 1
			frontier.append(v)
	return count

def remove_edges(rootgraph, root=1):
	cuts = 0
	for node in rootgraph[root]:
		if nodecount(node, rootgraph) % 2 == 0:
			cuts += 1
		cuts += remove_edges(rootgraph, node)
	return cuts
rootgraph = defaultdict(list)
(N, M) = input().split()
(N, M) = (int(N), int(M))
for _ in range(M):
	(ui, vi) = input().split()
	(ui, vi) = (int(ui), int(vi))
	rootgraph[vi].append(ui)
print(remove_edges(rootgraph))


def dfs(node):
	if node in visited:
		return 0
	visited[node] = 1
	children[node] = sum((dfs(i) for i in graph[node])) + 1
	return children[node]
(N, M) = [int(c) for c in input().split(' ')]
graph = {}
children = {}
visited = {}
for m in range(M):
	(ui, vi) = [int(c) for c in input().split(' ')]
	if ui not in graph:
		graph[ui] = []
	graph[ui].append(vi)
	if vi not in graph:
		graph[vi] = []
	graph[vi].append(ui)
root = list(graph.keys())[0]
dfs(root)
res = sum([1 if c & 1 == 0 else 0 for c in children.values()]) - 1
print(res)


import sys
sys.stdin.readline()
edge_list = [map(int, line.strip().split(' ')) for line in sys.stdin.readlines()]
adjacency_list = {}

def add_edge(a, b):
	cur_out = adjacency_list.get(a, set())
	cur_out.add(b)
	adjacency_list[a] = cur_out
for (a, b) in edge_list:
	add_edge(a, b)
	add_edge(b, a)

def process_node(n, parent=None):
	outgoing = adjacency_list[n]
	if parent:
		outgoing -= set([parent])
	size = 1
	cuts = 0
	if not outgoing:
		return (1, 0)
	else:
		for o in outgoing:
			(s, c) = process_node(o, n)
			size += s
			cuts += c
			if not s % 2:
				cuts += 1
				size -= s
	return (size, cuts)
print(process_node(1)[1])


import sys
__author__ = 'bbyk'

def read_tree(N):
	tree = dict()
	while N:
		(t, f) = [int(i) for i in cin.readline().split(' ', 1)]
		if f not in tree:
			tree[f] = [t]
		else:
			tree[f].append(t)
		N -= 1
	return tree

def num_to_remove(tree, node, cnt):
	if node not in tree:
		return 1
	sum = 1
	for i in tree[node]:
		ns = num_to_remove(tree, i, cnt)
		if not ns & 1:
			cnt[0] += 1
		else:
			sum += ns
	return sum
cin = None
if len(sys.argv) > 1:
	cin = open(sys.argv[1])
else:
	cin = sys.stdin
(N, M) = [int(i) for i in cin.readline().split(' ', 1)]
cnt = [0]
num_to_remove(read_tree(M), 1, cnt)
print(cnt[0])
if cin is not sys.stdin:
	cin.close()
pass


from sys import stdin

class Node(object):

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

	def add_child(self, child):
		self.children.append(child)

	def count_and_snip(self):
		vertices_count = snips_count = 0
		for child_number in self.children:
			child = vertices[child_number]
			(vc_child, sc_child) = child.count_and_snip()
			if 0 == vc_child % 2:
				snips_count += 1
			else:
				vertices_count += vc_child
			snips_count += sc_child
		else:
			vertices_count += 1
		return (vertices_count, snips_count)

	def __repr__(self):
		return '[{0}]'.format(', '.join(map(str, self.children)))
(vertices_count, edges_count) = list(map(int, stdin.readline().split()))
vertices = [Node() for i in range(vertices_count)]
for edge_number in range(edges_count):
	vertex_pair = list(map(int, stdin.readline().split()))
	vertices[vertex_pair[1] - 1].add_child(vertex_pair[0] - 1)
print(vertices[0].count_and_snip()[1])


def get_outgoing_edges(adjacency_list, root):
	vertices = []
	outgoing_edges = adjacency_list[root]
	for (vertex, edge) in enumerate(outgoing_edges):
		if edge:
			vertices.append(vertex)
	return vertices

def count_connected_vertices(adjacency_list, root):
	visited = [0 for _ in range(len(adjacency_list))]
	connected_vertices = 0
	stack = [root]
	while stack:
		root = stack.pop()
		visited[root] = 1
		connected_vertices += 1
		outgoing_edges = get_outgoing_edges(adjacency_list, root)
		for vertex in outgoing_edges:
			if not visited[vertex]:
				stack.append(vertex)
	return connected_vertices
(N, M) = [int(t) for t in input().split(' ')]
adjacency_list = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
for _ in range(M):
	(ui, vi) = [int(t) for t in input().split(' ')]
	adjacency_list[ui][vi] = 1
	adjacency_list[vi][ui] = 1
removed_edges = 0
for vertex in range(N + 1):
	outgoing_edges = get_outgoing_edges(adjacency_list, vertex)
	for destination in outgoing_edges:
		adjacency_list[vertex][destination] = 0
		adjacency_list[destination][vertex] = 0
		if count_connected_vertices(adjacency_list, destination) % 2:
			adjacency_list[vertex][destination] = 1
			adjacency_list[destination][vertex] = 1
		else:
			removed_edges += 1
print(removed_edges)


import sys

def get_children(graph, u, parent=None):
	res = []
	for x in range(1, len(graph)):
		if graph[u][x] == True and x != parent:
			res.append(x)
	return res

def count_nodes(graph, r, parent, child_count_seq):
	child_list = get_children(graph, r, parent)
	children_count_list = [count_nodes(graph, c, r, child_count_seq) for c in child_list]
	child_count_seq[r] = 1 + sum(children_count_list)
	return child_count_seq[r]
line1 = sys.stdin.readline().strip().split()
N = int(line1[0])
M = int(line1[1])
graph = [[False for j in range(N + 1)] for i in range(N + 1)]
for e_i in range(M):
	edge_line = sys.stdin.readline().strip().split()
	(u, v) = (int(edge_line[0]), int(edge_line[1]))
	graph[u][v] = True
	graph[v][u] = True
child_count_seq = [None for i in range(N + 1)]
count_nodes(graph, 1, None, child_count_seq)
res = 0
for i in range(len(child_count_seq)):
	x = child_count_seq[i]
	if x != None and i != 1 and (x % 2 == 0):
		res += 1
print(res)


(N, M) = [int(i) for i in input().split()]
(tree, numbers) = ([0 for i in range(N)], [1 for i in range(N)])
for _ in range(M):
	(u1, v1) = [int(i) for i in input().split()]
	(tree[u1 - 1], root) = (v1, tree[v1 - 1])
	numbers[v1 - 1] += numbers[u1 - 1]
	while root != 0:
		numbers[root - 1] += numbers[u1 - 1]
		root = tree[root - 1]
answer = -1
for i in numbers:
	if i % 2 == 0:
		answer += 1
print(answer)


def isEvenTree(edges, vertices):
	passedVertices = ()
	for vertex in vertices:
		if vertex not in passedVertices:
			passedVertices += (vertex,)
			stack = [vertex]
			countVerticesOnTree = 1
			while len(stack):
				vertex = stack.pop(0)
				for edge in edges:
					if vertex in edge:
						if vertex == edge[0]:
							neighbour = edge[1]
						else:
							neighbour = edge[0]
						if neighbour not in passedVertices:
							stack.insert(0, neighbour)
							passedVertices += (neighbour,)
							countVerticesOnTree += 1
			if countVerticesOnTree % 2 != 0:
				return False
	return True
(n, m) = [int(i) for i in input().split()]
vertices = tuple(range(1, n + 1))
edges = []
for i in range(m):
	edge = [int(i) for i in input().split()]
	edges.append(tuple(edge))
count = 0
flag = True
while flag:
	flag = False
	for edge in edges:
		t = edges[:]
		t.remove(edge)
		if isEvenTree(t, vertices):
			count += 1
			flag = True
			break
	if flag:
		edges.remove(edge)
print(count)


class Node:

	def __init__(self, index):
		self.index = index
		self.children = []

	def addChild(self, child):
		self.children.append(child)

	def countChildren(self):
		if not self.children:
			self.numOfChildren = 1
			return 1
		else:
			self.numOfChildren = 1 + sum(map(lambda n: n.countChildren(), self.children))
			return self.numOfChildren

def cuts(root):
	return len(list(filter(lambda n: n.numOfChildren % 2 == 0, root.children))) + sum(map(cuts, root.children))
(N, M) = list(map(int, input().split()))
tree = [Node(i) for i in range(N + 1)]
for _ in range(M):
	(c, p) = list(map(int, input().split()))
	tree[p].addChild(tree[c])
tree[1].countChildren()
print(cuts(tree[1]))


def tree_size(nodes, node):
	visited = [0] * len(nodes)

	def recurse(node):
		visited[node] = 1
		for neighbour in nodes[node]:
			if not visited[neighbour]:
				recurse(neighbour)
	recurse(node)
	return sum(visited)
(n, m) = map(int, input().split())
nodes = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	nodes[u].append(v)
	nodes[v].append(u)
removals = 0
while True:
	even_node = None
	for node in range(len(nodes)):
		if len(nodes[node]) % 2 == 0:
			even_node = node
			break
	else:
		break
	for neighbour in nodes[even_node]:
		nodes[even_node].remove(neighbour)
		nodes[neighbour].remove(even_node)
		if tree_size(nodes, neighbour) % 2 == 0:
			removals += 1
			break
		else:
			nodes[even_node].append(neighbour)
			nodes[neighbour].append(even_node)
print(removals)


class Node:

	def __init__(self, id):
		self.id = id
		self.parent = None
		self.child = set()
		self.total_children = None

	def __repr__(self):
		return 'N{}'.format(self.id)

	def add_child(self, child):
		self.child.add(child)
		child.parent = self

	def count_total_children(self):
		if self.total_children is None:
			self.total_children = sum((1 + c.count_total_children() for c in self.child))
		return self.total_children
(N, E) = [int(n) for n in input().strip().split()]
nodes = dict(((n, Node(n)) for n in range(1, N + 1)))
for e in range(E):
	(n1, n2) = [int(n) for n in input().strip().split()]
	nodes[n2].add_child(nodes[n1])
RESULT = 0
for n in nodes.values():
	children = n.count_total_children()
	if n.parent is None:
		continue
	if children % 2 == 1:
		RESULT += 1
print(RESULT)


def graf():
	(a, b) = [int(i) for i in input().split()]
	lst = [1] * a
	arr = [[0 for i in range(a)] for j in range(a)]
	for i in range(b):
		(x, y) = [int(i) for i in input().split()]
		arr[y - 1][x - 1] = 1
		arr[x - 1][y - 1] = 1
	flag = True
	while flag:
		for i in range(a):
			if sum(arr[i]) == 1:
				j = 0
				while 1:
					if arr[i][j] == 1:
						break
					j += 1
				if lst[i] % 2 != 0:
					lst[j] += lst[i]
					lst[i] = 0
				arr[i][j] = 0
				arr[j][i] = 0
		for i in lst:
			if i % 2 != 0:
				flag = True
				break
			else:
				flag = False
	answ = -1
	for i in lst:
		if i != 0:
			answ += 1
	print(answ)
graf()


def search(cur=0, last=None):
	summ = 0
	global count
	for x in range(n):
		if arr[cur][x] and x != last:
			z = search(x, cur)
			summ += z
			if not z % 2 and z:
				count += 1
	return summ + 1
(n, m) = list(map(int, input().split(' ')))
arr = [[False for y in range(n)] for x in range(n)]
for x in range(m):
	(a, b) = list(map(int, input().split(' ')))
	arr[a - 1][b - 1] = arr[b - 1][a - 1] = True
global count
count = 0
search()
print(count)


def search(forest, node_num, parent=-1):
	C = [search(forest, i, node_num) for i in forest[node_num] if i != parent]
	current_node_num = 1 + sum((c[0] for c in C))
	removed_edge_num = sum((c[1] for c in C)) + (current_node_num % 2 == 0)
	return (current_node_num, removed_edge_num)
(N, M) = map(int, input().strip().split())
forest = [[] for i in range(N + 1)]
for m in range(M):
	(a, b) = map(int, input().strip().split())
	forest[a].append(b)
	forest[b].append(a)
print(search(forest, 1)[1] - 1)


(N, M) = [int(i) for i in input().split(' ')]
nodes = {}
for _ in range(M):
	(u, v) = [int(i) for i in input().split(' ')]
	if u > v:
		(u, v) = (v, u)
	node = nodes.get(u)
	if not node:
		node = []
		nodes[u] = node
	node.append(v)

def forestCount(root):
	node = nodes.get(root)
	treeSize = 1
	removedEdges = 0
	if not node:
		return (treeSize, removedEdges)
	for child in node:
		(subtreeSize, subtreeRemovedEdges) = forestCount(child)
		removedEdges += subtreeRemovedEdges
		if subtreeSize % 2 == 0:
			removedEdges += 1
		else:
			treeSize += subtreeSize
	return (treeSize, removedEdges)
(_, removedEdges) = forestCount(min(nodes.keys()))
print(removedEdges)


def graf():
	(a, b) = [int(i) for i in input().split()]
	lst = [1] * a
	arr = [[0 for i in range(a)] for j in range(a)]
	for i in range(b):
		(x, y) = [int(i) for i in input().split()]
		arr[y - 1][x - 1] = 1
		arr[x - 1][y - 1] = 1
	flag = True
	while flag:
		for i in range(a):
			if sum(arr[i]) == 1:
				j = 0
				while 1:
					if arr[i][j] == 1:
						break
					j += 1
				if lst[i] % 2 != 0:
					lst[j] += lst[i]
					lst[i] = 0
				arr[i][j] = 0
				arr[j][i] = 0
		for i in lst:
			if i % 2 != 0:
				flag = True
				break
			else:
				flag = False
	answ = -1
	for i in lst:
		if i != 0:
			answ += 1
	print(answ)
graf()


def getCount(node, par, adjlst):
	if len(adjlst[node]) == 1:
		return (1, 0)
	ans = 0
	count = 0
	for nd in adjlst[node]:
		if nd != par:
			(tcount, tans) = getCount(nd, node, adjlst)
			ans += tans
			count += tcount
			if tcount % 2 == 0:
				ans += 1
	count += 1
	return (count, ans)
line = input().split()
N = int(line[0])
adjlst = []
for i in range(N + 1):
	adjlst.append([])
for i in range(N - 1):
	line = input().split()
	x = int(line[0])
	y = int(line[1])
	adjlst[x].append(y)
	adjlst[y].append(x)
adjlst[0].append(1)
adjlst[1].append(0)
(count, ans) = getCount(1, 0, adjlst)
print(str(ans))


__author__ = 'max'
import collections

class Node:

	def __init__(self, ident):
		self.ident = ident
		self.adj_list = []
		self.parent_ident = None
		self.subtree_size = 0

	def children(self):
		return (node for node in self.adj_list if node.ident != self.parent_ident)

	def set_parent(self, parent_ident):
		self.parent_ident = parent_ident

class Tree:

	def __init__(self, node_count):
		self.nodes = [Node(ident) for ident in range(1, node_count + 1)]
		self.root = self.nodes[0]
		self.is_rooted_tree = False

	def get_node(self, ident):
		return self.nodes[ident - 1]

	def add_edge(self, ident1, ident2):
		node1 = self.get_node(ident1)
		node2 = self.get_node(ident2)
		node1.adj_list.append(node2)
		node2.adj_list.append(node1)

	def convert_to_rooted_tree(self):
		if self.is_rooted_tree:
			return
		self._init_parent_pointers()
		self._init_subtree_sizes(self.root)
		self.is_rooted_tree = True

	def _init_parent_pointers(self):
		parent_nodes = collections.deque([self.root])
		while parent_nodes:
			parent = parent_nodes.popleft()
			for child in parent.children():
				child.parent_ident = parent.ident
				parent_nodes.append(child)

	def _init_subtree_sizes(self, node):
		node.subtree_size = 1
		for child in node.children():
			self._init_subtree_sizes(child)
			node.subtree_size += child.subtree_size

def get_edge_remove_count_for_even_forest(tree):
	edge_remove_count = 0
	nodes = collections.deque([tree.root])
	while nodes:
		node = nodes.popleft()
		for child in node.children():
			nodes.append(child)
			if child.subtree_size % 2 == 0:
				edge_remove_count += 1
	return edge_remove_count

def main():
	(node_count, edge_count) = [int(num) for num in input().split()]
	tree = Tree(node_count)
	for i in range(edge_count):
		(ident1, ident2) = [int(num) for num in input().split()]
		tree.add_edge(ident1, ident2)
	tree.convert_to_rooted_tree()
	print(get_edge_remove_count_for_even_forest(tree))
main()


(n, m) = str(input()).split()
(n, m) = (int(n), int(m))
adjList = [[] for x in range(0, n + 1)]
for i in range(0, m):
	(x, y) = str(input()).split()
	(x, y) = (int(x), int(y))
	adjList[x].append(y)
	adjList[y].append(x)

def solve(adjList, n, m):
	visited = [False for x in range(0, n + 1)]
	count = [0 for x in range(0, n + 1)]
	adjListNew = [[] for x in range(0, n + 1)]
	ans = m

	def dfs(n):
		c = 0
		visited[n] = True
		for x in adjList[n]:
			if visited[x] == False:
				adjListNew[n].append(x)
				c += dfs(x)
		count[n] = c + 1
		return c + 1

	def dfs2(n):
		for x in adjListNew[n]:
			if count[x] % 2 == 0 and (count[n] - count[x]) % 2 == 0:
				count[n] -= count[x]
				nonlocal ans
				ans -= 1
			else:
				count[x] = count[n]
			dfs2(x)
	dfs(7)
	dfs2(7)
	return ans
ans = solve(adjList, n, m)
print(m - ans)


def vert_number(edges, counted, v):
	ret = 0
	children = [x[1] for x in edges if x[0] == v and x[1] not in counted]
	counted.append(v)
	for child in children:
		ret += vert_number(edges, counted, child)
	return ret + len(children)
s = input()
ar = s.split()
n = int(ar[0])
m = int(ar[1])
edges = []
for ind in range(m):
	s = input()
	ar = s.split()
	edges.append((int(ar[0]), int(ar[1])))
	edges.append((int(ar[1]), int(ar[0])))
cnt = 0
for item in edges.copy():
	if item in edges:
		edges.remove(item)
		edges.remove((item[1], item[0]))
		a = vert_number(edges, [], item[0]) + 1
		b = vert_number(edges, [], item[1]) + 1
		if a % 2 == 0 and b % 2 == 0:
			cnt += 1
		else:
			edges.append(item)
			edges.append((item[1], item[0]))
print(cnt)


(N, M) = list(map(int, input().split()))
edges = {}
for edge in range(M):
	(u, v) = list(map(int, input().split()))
	if not v in edges:
		edges[v] = []
	edges[v].append(u)

def nr_of_children(node):
	if not node in edges:
		return 0
	total = 0
	for child in edges[node]:
		total += 1 + nr_of_children(child)
	return total

def node_even(node):
	return (nr_of_children(node) + 1) % 2 == 0
even_count = -1
for i in range(1, N + 1):
	if node_even(i):
		even_count += 1
print(even_count)


import copy

def readinpline():
	inpstr = input().strip().split(' ')
	n = int(inpstr[0])
	m = int(inpstr[1])
	return (n, m)
(vert, edge) = readinpline()
edgedict = {}
for i in range(edge):
	(vi, ui) = readinpline()
	edgedict[i] = {}
	edgedict[i]['dst'] = vi
	edgedict[i]['src'] = ui

def getelem(node, edgedicts):
	elemtree = [node]
	for elm in elemtree:
		for key in edgedicts:
			if elm == edgedicts[key]['src']:
				dst = edgedicts[key]['dst']
				if dst not in elemtree:
					elemtree.append(dst)
			elif elm == edgedicts[key]['dst']:
				dst = edgedicts[key]['src']
				if dst not in elemtree:
					elemtree.append(dst)
	return elemtree

def getnumofchildnodes(src, dst, newedgedict):
	lstl = getelem(src, newedgedict)
	lstr = getelem(dst, newedgedict)
	return (len(lstl), len(lstr))
for i in range(edge):
	newedgedict = copy.copy(edgedict)
	src = newedgedict[i]['src']
	dst = newedgedict[i]['dst']
	del newedgedict[i]
	(lchn, rchn) = getnumofchildnodes(src, dst, newedgedict)
	if lchn % 2 == 0 and rchn % 2 == 0:
		edgedict = newedgedict
print(edge - len(edgedict))


__author__ = 'KaunilD'
(N, M) = input().split()
N = int(N)
M = int(M)
child = {}
tree = {}
for i in range(1, M + 1):
	(ui, vi) = input().split()
	ui = int(ui)
	vi = int(vi)
	if vi not in tree.keys():
		tree[vi] = [ui]
	else:
		tree[vi].append(ui)
	child[i] = 1
for i in range(M + 1, 1, -1):
	if i not in tree.keys():
		child[i] = 1
	else:
		for j in tree[i]:
			child[i] = child[i] + child[j]
count = 0
for i in range(1, M + 1):
	if child[i] % 2 == 0:
		count += 1
print(count)


from copy import deepcopy

def remove_vertex(v, tree):
	tree.pop(v, 0)
	for k in tree:
		if v in tree[k]:
			tree[k].remove(v)
	return tree

def extract_tree(forest, vertex):
	old_vertices = set([vertex])
	new_vertices = set([vertex])
	total_vertices = set([vertex])
	while new_vertices != set():
		for v in old_vertices:
			new_vertices |= set(forest[v])
		new_vertices -= total_vertices
		old_vertices = deepcopy(new_vertices)
		total_vertices |= new_vertices
	return {v: forest[v] for v in total_vertices}

def remove_edge(edge, tree):
	tree_0 = deepcopy(tree)
	tree_1 = deepcopy(tree)
	tree_1 = remove_vertex(edge[0], tree_1)
	tree_0 = remove_vertex(edge[1], tree_0)
	return (extract_tree(tree_0, edge[0]), extract_tree(tree_1, edge[1]))
(N_s, M_s) = input().split()
(N, M) = (int(N_s), int(M_s))
edges = []
for e in range(M):
	edge_s = input().split()
	edge = [int(v) for v in edge_s]
	edges.append(edge)
tree = {}
for v in range(1, N + 1):
	tree[v] = []
for e in edges:
	tree[e[0]].append(e[1])
	tree[e[1]].append(e[0])
counter = 0
for e in edges:
	if len(remove_edge(e, tree)[0]) % 2 == 0:
		counter += 1
print(counter)


class Vertex:

	def __init__(self, key):
		self.id = key
		self.connectedTo = {}
		self.pred = None
		self.color = 'white'
		self.children = 0

	def addNeighbor(self, nbr, weight=0):
		self.connectedTo[nbr] = weight

	def __str__(self):
		return str(self.id) + ' connected to: ' + str([x.id for x in self.connectedTo]) + ' children ' + str(self.children) + ' color ' + self.color

	def getConnections(self):
		return self.connectedTo.keys()

	def getId(self):
		return self.id

	def getPred(self):
		return self.pred

	def setPred(self, value):
		self.pred = value

	def getColor(self):
		return self.color

	def setColor(self, newColor):
		self.color = newColor

	def getChildren(self):
		return self.children

	def setChildren(self, newChildren):
		self.children = newChildren

class Graph:

	def __init__(self):
		self.vertList = {}
		self.numVertices = 0

	def addVertex(self, key):
		self.numVertices = self.numVertices + 1
		newVertex = Vertex(key)
		self.vertList[key] = newVertex
		return newVertex

	def getVertex(self, n):
		if n in self.vertList:
			return self.vertList[n]
		else:
			return None

	def __contains__(self, n):
		return n in self.vertList

	def addEdge(self, f, t, cost=0):
		if f not in self.vertList:
			nv = self.addVertex(f)
		if t not in self.vertList:
			nv = self.addVertex(t)
		self.vertList[f].addNeighbor(self.vertList[t], cost)
		self.vertList[t].addNeighbor(self.vertList[f], cost)

	def getVertices(self):
		return self.vertList.keys()

	def __iter__(self):
		return iter(self.vertList.values())

def evenTree(g):
	removed = 0
	start = getMaxByConnectedTo(g)
	dfs(g, start)
	for v in g:
		if v.getChildren() % 2 == 0:
			removed += 1
	return removed - 1

def getMaxByConnectedTo(g):
	maxVertex = None
	for v in g:
		if maxVertex == None:
			maxVertex = v
		elif len(v.getConnections()) > len(maxVertex.getConnections()):
			maxVertex = v
	return maxVertex

def dfs(g, currentVert):
	currentVert.setPred(None)
	currentVert.setColor('gray')
	for nbr in currentVert.getConnections():
		if nbr.getColor() == 'white':
			nbr.setPred(currentVert)
			dfs(g, nbr)
			currentVert.setChildren(currentVert.getChildren() + nbr.getChildren())
	currentVert.setChildren(currentVert.getChildren() + 1)
	currentVert.setColor('black')
(N, M) = (int(x) for x in input().split())
g = Graph()
for i in range(M):
	(fromVertex, toVertex) = (int(y) for y in input().split())
	g.addEdge(fromVertex, toVertex)
print(evenTree(g))


from collections import defaultdict

def _count_children(tree, node):
	if node not in tree:
		return 0
	count = len(tree[node])
	for adj in tree[node]:
		count += _count_children(tree, adj)
	return count

def count_edges(tree):
	count = 0
	for node in tree:
		if _count_children(tree, node) % 2 != 0:
			count += 1
	return count - 1
tree = defaultdict(set)
(m, n) = input().strip().split()
for _ in range(int(n)):
	(v, w) = input().strip().split()
	tree[w].add(v)
print(count_edges(tree))


from collections import defaultdict
global counter

def countNodes(D, N, ret):
	L = D[N]
	global counter
	counter += len(L)
	for x in L:
		countNodes(D, x, False)
	if ret:
		return counter
(V, E) = list(map(int, input().split()))
L = []
D = defaultdict(list)
answer = 0
for x in range(E):
	(e2, e1) = list(map(int, input().split()))
	D[e1].append(e2)
	L.append([e1, e2])
for x in L:
	counter = 1
	if countNodes(D, x[1], True) % 2 == 0:
		D[x[0]].remove(x[1])
		answer += 1
print(answer)


def countCuts(node):
	count = 0
	for n in node.children:
		if n.isEven():
			count += 1
		count += countCuts(n)
	return count

def findRoot(array):
	for n in array:
		if not n.hasParent():
			return n

class Node:

	def __init__(self, i):
		self.children = []
		self.id = i
		self.parent = None

	def addChild(self, node):
		self.children.append(node)
		node.parent = self

	def degree(self):
		return len(self.children)

	def ancestors(self):
		count = 1
		for n in self.children:
			count += n.ancestors()
		return count

	def isEven(self):
		return self.ancestors() % 2 == 0

	def hasParent(self):
		return self.parent is not None
(NumVerts, NumEdges) = map(int, input().split(' '))
vertices = []
for i in range(NumVerts):
	vertices.append(Node(i + 1))
for i in range(NumEdges):
	(u, v) = map(int, input().split(' '))
	(u, v) = (u - 1, v - 1)
	if vertices[u].hasParent():
		(u, v) = (v, u)
	vertices[v].addChild(vertices[u])
print(countCuts(findRoot(vertices)))


def weightFactory(graph):
	found_weight = {}

	def weight(node, parent):
		if (node, parent) not in found_weight:
			found_weight[node, parent] = 1 + sum((weight(child, node) for child in graph[node] if child != parent))
		return found_weight[node, parent]
	return weight

def edgeCutFactory(graph):
	weight = weightFactory(graph)

	def edgeCut(node, parent):
		cuts_below = sum((edgeCut(child, node) for child in graph[node] if child is not parent))
		can_cut_parent_edge = parent and (not weight(node, parent) % 2)
		return cuts_below + 1 if can_cut_parent_edge else cuts_below
	return edgeCut

def loadGraph():
	(V, E) = map(int, input().split(' '))
	graph = []
	for v in range(V + 1):
		graph.append([])
	for e in range(E):
		(v1, v2) = map(int, input().split(' '))
		graph[v1].append(v2)
		graph[v2].append(v1)
	return graph

def main():
	graph = loadGraph()
	edgeCut = edgeCutFactory(graph)
	print(edgeCut(1, None))
main()


import sys

def readGraph(graphString):
	graph = {}
	for edge in graphString.split(','):
		e = list(map(int, edge.split(' ')))
		if e[0] in graph:
			graph[e[0]].append(e[1])
		else:
			graph[e[0]] = [e[1]]
		if e[1] in graph:
			graph[e[1]].append(e[0])
		else:
			graph[e[1]] = [e[0]]
	return graph

def split(a, b, graph):
	graphc = graph.copy()
	graphc[a] = graphc[a].copy()
	graphc[b] = graphc[b].copy()
	graphc[a].remove(b)
	graphc[b].remove(a)
	return graphc

def compSize(start, graph, seen):
	if start in seen:
		return 0
	else:
		seen.append(start)
		return 1 + sum([compSize(i, graph, seen) for i in graph[start] if not i in seen])

def getMaxEdges(graph):
	g = graph
	c = 0
	cont = True
	while cont:
		cont = False
		for sp in g.keys():
			pot = g[sp]
			if len(pot) > 1:
				for i in pot:
					g2 = split(sp, i, g)
					if compSize(sp, g2, []) % 2 == 0 and compSize(i, g2, []) % 2 == 0:
						g = g2
						c += 1
						cont = True
	return c
t = ','.join(list(sys.stdin)[1:])
print(getMaxEdges(readGraph(t)))


(n, m) = map(int, input().split())
mtx = [[0] * n for _ in range(n)]
for _ in range(m):
	(e, s) = map(int, input().split())
	mtx[e - 1][s - 1] = 1
for k in range(n):
	for i in range(n):
		for j in range(n):
			if mtx[i][k] == 1 and mtx[k][j] == 1:
				mtx[i][j] = 1
cs = sum([1 for i in map(sum, zip(*mtx)) if i % 2 == 1])
print(cs - 1)


def is_leaf(v, adj_matrix):
	return 1 == sum(adj_matrix[v])

def find_leaf_parent(v, adj_matrix):
	for (p, adj) in enumerate(adj_matrix[v]):
		if 1 == adj:
			return p
	return None

def remove_leaf(v, p, adj_matrix):
	adj_matrix[v][p] = 0
	adj_matrix[p][v] = 0

def solve(adj_matrix, counters):
	removed = 0
	has_vertices = False
	for v in range(len(adj_matrix)):
		if is_leaf(v, adj_matrix):
			has_vertices = True
			p = find_leaf_parent(v, adj_matrix)
			remove_leaf(v, p, adj_matrix)
			counters[p] += 1 + counters[v]
			if 1 == counters[v] % 2:
				removed += 1
	if not has_vertices:
		return 0
	return removed + solve(adj_matrix, counters)
(nv, ne) = map(int, input().split(' '))
matrix = [[0] * nv for i in range(nv)]
for _ in range(ne):
	(v1, v2) = map(int, input().split(' '))
	matrix[v1 - 1][v2 - 1] = 1
	matrix[v2 - 1][v1 - 1] = 1
print(solve(matrix, {v: 0 for v in range(len(matrix))}))


(N, M) = [int(x) for x in input().split()]
edge_dict = {}
visited = set([])

def add_edge_to(start_v, end_v, edge_dict):
	if not start_v in edge_dict:
		edge_dict[start_v] = []
	edge_dict[start_v].append(end_v)
for _ in range(M):
	(v1, v2) = [int(x) for x in input().split()]
	add_edge_to(v1, v2, edge_dict)
	add_edge_to(v2, v1, edge_dict)
splits = 0

def tree_size(root, parent):
	my_neighbours = edge_dict[root]
	accum = 1
	if len(my_neighbours) > 1:
		for neigh in my_neighbours:
			if neigh not in visited and neigh != parent:
				accum += tree_size(neigh, root)
	return accum
for vertice in edge_dict.keys():
	visited.add(vertice)
	for neighbour in edge_dict[vertice]:
		if neighbour not in visited and tree_size(neighbour, vertice) % 2 == 0:
			splits += 1
print(splits)


def even(n):
	return n % 2 == 0

def num_connected(edges, verts, v1, exclude):
	connected = [v1]
	also = []
	for edge in edges[verts.index(v1)]:
		if edge not in connected and edge != exclude:
			connected.append(edge)
			also.append(edge)
	for vert in also:
		for edge in edges[verts.index(vert)]:
			if edge not in connected and edge != exclude:
				connected.append(edge)
				also.append(edge)
	return len(connected)

def cut_edges(edges, verts, edge_count):
	num_cut_edges = 0
	n = len(verts)
	keep = True
	while keep:
		keep = False
		for i in range(n):
			if even(len(edges[i])):
				tmp_vert_i = verts[i]
				for j in range(len(edges[i])):
					tmp_vert_j = edges[i][j]
					conn_vert = num_connected(edges, verts, tmp_vert_j, tmp_vert_i)
					if even(conn_vert):
						edges[i].remove(tmp_vert_j)
						edges[verts.index(tmp_vert_j)].remove(tmp_vert_i)
						num_cut_edges += 1
						keep = True
						break
	return num_cut_edges
first = input().strip().split()
n = int(first[0])
m = int(first[1])
verts = []
edges = []
for i in range(m):
	nums = input().strip().split()
	a = int(nums[0])
	b = int(nums[1])
	if a in verts:
		edges[verts.index(a)].append(b)
	else:
		verts.append(a)
		edges.append([b])
	if b in verts:
		edges[verts.index(b)].append(a)
	else:
		verts.append(b)
		edges.append([a])
print(cut_edges(edges, verts, m))


import sys

def inp():
	return list(map(int, input().split()))
(n_v, t) = inp()
n_v += 1
visited = None
noofedgestorem = None

def f_(g, s):
	global visited, noofedgestorem
	visited[s] = False
	child_count = 0
	for i in g[s]:
		if visited[i] is None:
			child_count += 1
			subtreechildcount = f_(g, i)
			if subtreechildcount % 2 == 1:
				noofedgestorem += 1
			child_count += subtreechildcount
	visited[s] = True
	return child_count

def f(g):
	global visited, noofedgestorem
	visited = [None for _ in range(len(g))]
	noofedgestorem = 0
	for i in range(1, len(g)):
		if visited[i] is None:
			f_(g, i)
		elif visited[i] is False:
			print('ERR..', i, 'visited', visited, file=sys.stderr)
	return noofedgestorem
g = [[] for _ in range(n_v)]
for _ in range(t):
	(i, j) = inp()
	g[i].append(j)
	g[j].append(i)
print(f(g))


from collections import defaultdict

def empty_list():
	return []

def handle_node(e, n):
	if n not in e:
		return (1, 0)
	desc = 0
	cut = 0
	for child in e[n]:
		(curr_desc, curr_cut) = handle_node(e, child)
		cut += curr_cut
		if curr_desc % 2 == 0:
			cut += 1
		else:
			desc += curr_desc
	return (desc + 1, cut)
(N, M) = list(map(int, input().split(' ')))
e = defaultdict(empty_list)
p = {}
for i in range(M):
	(ui, vi) = list(map(int, input().split(' ')))
	(ui, vi) = (min(ui, vi), max(ui, vi))
	e[ui - 1].append(vi - 1)
	p[vi - 1] = ui - 1
root = p.keys().__iter__().__next__()
while root in p:
	root = p[root]
print(handle_node(e, root)[1])


from queue import Queue
import copy
import random

def max_even_forest(graph):
	stack = []
	parents = {}
	nodes = list(graph.keys())
	root = nodes[random.randint(0, len(nodes))]
	q = Queue()
	q.put(root)
	stack.append(root)
	while not q.empty():
		node = q.get()
		for nbr in graph[node]:
			if nbr not in stack:
				q.put(nbr)
				parents[nbr] = node
				stack.append(nbr)
	subtree_size = {}
	while len(stack) > 1:
		node = stack.pop()
		subtree_size[node] = 1
		neighbors = copy.copy(graph[node])
		neighbors.remove(parents[node])
		for nbr in neighbors:
			subtree_size[node] += subtree_size[nbr]
	count = 0
	for node in subtree_size:
		if subtree_size[node] % 2 == 0:
			count += 1
	return count

def run():
	line = input()
	num_vertices = int(line.split()[0])
	num_edges = int(line.split()[1])
	graph = {}
	for idx in range(1, num_vertices + 1):
		graph[idx] = []
	for dummy in range(num_edges):
		line = input()
		node1 = int(line.split()[0])
		node2 = int(line.split()[1])
		graph[node1].append(node2)
		graph[node2].append(node1)
	print(max_even_forest(graph))
run()


import fileinput
import random
graph = {}
edge_count = {}
vertex_count = {}
visited = set()
edges_to_remove = set()

def dfs(node):
	visited.add(node)
	adjacent = set(graph[node])
	not_visited = adjacent.difference(visited)
	if len(not_visited) == 0:
		return 1
	else:
		while not_visited:
			next = random.sample(not_visited, 1)[0]
			not_visited.remove(next)
			if node not in edge_count:
				edge_count[node] = {}
			edge_count[node][next] = dfs(next)
			if edge_count[node][next] % 2 == 0:
				edges_to_remove.add((node, next))
		return 1 + sum(edge_count[node].values())

def even_tree():
	i = 0
	for line in fileinput.input():
		i += 1
		if i == 1:
			continue
		vertices = line.strip().split(' ')
		vertex_count[vertices[0]] = 0
		vertex_count[vertices[1]] = 0
		if vertices[0] not in graph:
			graph[vertices[0]] = []
		if vertices[1] not in graph:
			graph[vertices[1]] = []
		graph[vertices[0]].append(vertices[1])
		graph[vertices[1]].append(vertices[0])
	root = random.sample(set(vertex_count.keys()), 1)[0]
	dfs(root)
	return edges_to_remove
print(len(even_tree()))


from collections import defaultdict

def size(root, edges):
	if root not in edges:
		return 1
	else:
		return 1 + sum([size(child, edges) for child in edges[root]])
eedges = []

def even_edges(root, edges):
	if edges[root]:
		for child in edges[root]:
			if size(child, edges) % 2 == 0:
				eedges.append([root, child])
			even_edges(child, edges)
(N, M) = [int(i) for i in input().split()]
E = defaultdict(list)
for m in range(M):
	edge = [int(i) for i in input().split()]
	E[edge[1]] += [edge[0]]
even_edges(1, E)
print(len(eedges))


from collections import defaultdict

def getRemovedEdgeCount(tree):
	visitedNodes = set()
	subtreeSizes = {}

	def visit(node):
		visitedNodes.add(node)
		unvisitedNeighbors = tree[node] - visitedNodes
		for neighbor in unvisitedNeighbors:
			visit(neighbor)
		subtreeSizes[node] = sum((1 + subtreeSizes[neighbor] for neighbor in unvisitedNeighbors))
	for node in tree:
		if node not in visitedNodes:
			visit(node)
	return sum((1 for n in subtreeSizes if subtreeSizes[n] > 0 and subtreeSizes[n] % 2 == 1)) - 1
(nodeCount, edgeCount) = [int(x) for x in input().split(' ')]
tree = defaultdict(set)
for _ in range(edgeCount):
	(node1, node2) = [int(x) for x in input().split(' ')]
	tree[node1].add(node2)
	tree[node2].add(node1)
print(getRemovedEdgeCount(tree))


def even_vertices(edges):
	connected_component_id = 0
	vertices = {}
	duplicates = {}
	for e in edges:
		(a, b) = e
		if a in vertices and b not in vertices:
			vertices[b] = vertices[a]
		elif b in vertices and a not in vertices:
			vertices[a] = vertices[b]
		elif a not in vertices and b not in vertices:
			vertices[a] = vertices[b] = connected_component_id
			connected_component_id += 1
		elif vertices[a] != vertices[b]:
			duplicates[vertices[a]] = vertices[b]
	components = {}
	for comp in vertices.values():
		comp_id = comp
		while comp_id in duplicates:
			comp_id = duplicates[comp_id]
		n = components[comp_id] + 1 if comp_id in components else 1
		components[comp_id] = n
	if len(components) <= 1:
		return False
	else:
		return all([n % 2 == 0 for n in components.values()])

def possible_splits(edges):
	res = 0
	for i in range(len(edges)):
		if even_vertices(edges[:i] + edges[i + 1:]):
			res += 1
	return res
(n, m) = [int(s) for s in input().split()]
edges = []
for _ in range(m):
	edges.append([int(s) for s in input().split()])
print(possible_splits(edges))


def oddNodes(n, adjList):
	odd = True
	for child in adjList[n]:
		odd = odd ^ oddNodes(child, adjList)
	return odd

def numRemoved(n, adjList):
	sum = 0
	for child in adjList[n]:
		if not oddNodes(child, adjList):
			sum += 1 + numRemoved(child, adjList)
		else:
			sum += numRemoved(child, adjList)
	return sum
from collections import defaultdict
(v, e) = [int(x) for x in input().split()]
adjList = defaultdict(list)
for _ in range(e):
	unsorted = [int(x) for x in input().split()]
	unsorted.sort()
	adjList[unsorted[0]].append(unsorted[1])
print(numRemoved(1, adjList))


from collections import defaultdict

def main():
	(n, m) = readints()
	edgelist = []
	for _ in range(m):
		edgelist.append(readints())
	print(maxremove(edgelist))

def readints():
	return [int(fld) for fld in input().split()]

def maxremove(edgelist):
	(root, children, treesize) = reformat(edgelist)
	return countremove(root, children, treesize)

def countremove(root, children, treesize):
	count = 0
	for child in children[root]:
		if treesize[child] & 1 == 0:
			count += 1
		count += countremove(child, children, treesize)
	return count

def reformat(edgelist):
	nbrs = defaultdict(list)
	for (x, y) in edgelist:
		nbrs[x].append(y)
		nbrs[y].append(x)
		root = x
	(children, treesize) = ({}, {})
	buildtbls(None, root, children, treesize, nbrs)
	return (root, children, treesize)

def buildtbls(prev, root, children, treesize, nbrs):
	children[root] = c = [child for child in nbrs[root] if child != prev]
	for child in c:
		buildtbls(root, child, children, treesize, nbrs)
	treesize[root] = 1 + sum((treesize[child] for child in c))
	return
main()


(n, m) = [int(j) for j in input().split()]
edges = [[int(j) for j in input().split()] for _ in range(m)]
subtree_vertice_count = [1 for _ in range(n)]

def is_divisable(dividant, divider):
	return float(dividant) / float(divider) == int(float(dividant) / float(divider))

class Node:
	id = 0
	count = []
	neighbor = []
	total_count = 1

	def __init__(self, id):
		self.id = id
		self.count = []
		self.neighbor = []
		self.total_count = 1

	def extend(self, father, vertice_count):
		self.total_count += vertice_count
		for i in range(len(self.count)):
			if self.neighbor[i] != father:
				self.count[i] += vertice_count
				self.neighbor[i].extend(self, vertice_count)

	def __str__(self):
		string = '[id=' + str(self.id + 1) + ' total=' + str(self.total_count) + ' '
		for i in range(len(self.count)):
			string += '(' + str(self.neighbor[i].id + 1) + ':' + str(self.count[i]) + '),'
		string += ']'
		return string
nodes = [Node(i) for i in range(n)]
for e in edges:
	nodes[e[0] - 1].count.append(nodes[e[0] - 1].total_count)
	nodes[e[0] - 1].neighbor.append(nodes[e[1] - 1])
	nodes[e[1] - 1].count.append(nodes[e[1] - 1].total_count)
	nodes[e[1] - 1].neighbor.append(nodes[e[0] - 1])
	total_count = nodes[e[0] - 1].total_count
	nodes[e[0] - 1].extend(nodes[e[1] - 1], nodes[e[1] - 1].total_count)
	nodes[e[1] - 1].extend(nodes[e[0] - 1], total_count)
sum_even = 0
for i in range(n):
	for j in range(len(nodes[i].count)):
		if is_divisable(nodes[i].count[j], 2):
			sum_even += 1
print(int(sum_even / 2))


def get_connected_vertices(edges, v, not_vs=[]):
	vertices = [v]
	connected_edges = [e for e in edges if v in e]
	for edge in connected_edges:
		other_v = edge[(edge.index(v) + 1) % 2]
		if other_v not in not_vs:
			vertices.append(other_v)
			vertices += get_connected_vertices(edges, other_v, vertices)
	return list(set(vertices))

def is_deletable(edges, edge):
	new_edges = [e for e in edges if e != edge]
	return False not in [len(get_connected_vertices(new_edges, v)) % 2 == 0 for v in edge]
(num_vertices, num_edges) = map(int, input().split(' '))
edges = []
for i in range(0, num_edges):
	edges.append(tuple(map(int, input().split(' '))))
print(len([e for e in edges if is_deletable(edges, e)]))


(N, K) = [int(x) for x in input().split()]
tree = dict(([int(x) for x in input().split()] for _ in range(K)))
res = 0
for lower in range(2, K + 2):
	size = 1
	for branch in range(lower + 1, K + 2):
		end = branch
		while end != lower and end != 1:
			end = tree[end]
		if end == lower:
			size += 1
	if size % 2 == 0:
		res += 1
print(res)


tree = []
count = []
import sys
head = [int(n) for n in input().split()]
N = head[0]
M = head[1]
for i in range(N):
	count.append(1)
	tree.append(int(0))
for i in range(M):
	line = [int(n) for n in input().split()]
	u1 = line[0]
	v1 = line[1]
	tree[u1 - 1] = v1
	count[v1 - 1] += count[u1 - 1]
	root = tree[v1 - 1]
	while root != 0:
		count[root - 1] += count[u1 - 1]
		root = tree[root - 1]
sys.stdout.write('')
counter = -1
for i in range(len(count)):
	if count[i] % 2 == 0:
		counter += 1
sys.stdout.write(str(counter))


(n, m) = [int(x) for x in input().split()]
graph = {}
for x in range(1, n + 1):
	graph[x] = []
for x in range(0, m):
	(i, j) = [int(x) for x in input().split()]
	graph[i].append(j)
	graph[j].append(i)

def getNumChildren(G, cur, visited):
	num = 0
	for child in G[cur]:
		if child not in visited:
			visited.append(child)
			num += 1 + getNumChildren(G, child, visited)
	return num
cuts = 0
for x in graph:
	evensubtrees = 0
	oddsubtrees = 0
	for child in graph[x]:
		visited = [x, child]
		numChildren = getNumChildren(graph, child, visited)
		if numChildren == 0:
			continue
		elif numChildren % 2 is 0:
			continue
		else:
			cuts += 1
print(int(cuts / 2))


(n, v) = map(int, input().split())
par = [None] * (n + 1)
child = [0] * (n + 1)
for i in range(1, v + 1):
	(c, p) = map(int, input().split())
	par[c] = p
	child[p] += 1
	while p != 1:
		p = par[p]
		child[p] += 1
cut = 0
for j in range(2, n + 1):
	if child[j] % 2 == 1:
		cut += 1
print(cut)


class Node:

	def __init__(self, name):
		self.children = []
		self.name = name

	def __str__(self):
		return str(self.name)

	def __repr__(self):
		return str(self.name)

	def breit(self, t=-1, br=None):
		if br is None:
			br = []
		if t == -1:
			for x in range(0, self.tiefe() + 1):
				br.append(self.breit(x))
		elif t == 0:
			br.append(self)
		else:
			for c in self.children:
				c.breit(t - 1, br)
		return br

	def tiefe(self):
		return max(map(Node.tiefe, self.children)) + 1 if len(self.children) > 0 else 0

	def __len__(self):
		return sum(map(len, self.children)) + 1

	def do(self):
		if len(self) <= 2:
			return 0
		cuts = 0
		for c in self.children:
			if len(c) % 2 == 0:
				cuts += 1 + c.do()
			else:
				cuts += c.do()
		return cuts
(vc, ec) = list(map(int, input().split()))
nodes = [Node(x + 1) for x in range(0, vc)]
for i in range(0, ec):
	(child, parent) = list(map(int, input().split()))
	nodes[parent - 1].children.append(nodes[child - 1])
root = nodes[0]
print(root.do())


def subtree_vertex_cnt(node, ancestors, adj):
	cnt = 1
	neighbours = set(adj[node])
	neighbours.difference_update(ancestors)
	degree = len(neighbours)
	if degree == 0:
		return cnt
	new_ancestors = set(ancestors)
	new_ancestors.add(node)
	for neighbour in neighbours:
		cnt += subtree_vertex_cnt(neighbour, new_ancestors, adj)
	return cnt
adj = dict()
(v, e) = [int(x) for x in input().strip().split(' ')]
for i in range(e):
	(p, q) = [int(x) for x in input().strip().split(' ')]
	if p in adj:
		adj[p].append(q)
	else:
		adj[p] = [q]
	if q in adj:
		adj[q].append(p)
	else:
		adj[q] = [p]
cnt = 0
edge_removed = True
while edge_removed:
	edge_removed = False
	for vertex in range(1, v + 1):
		neighbours = list(adj[vertex])
		degree = len(neighbours)
		if degree == 0:
			continue
		if degree % 2 == 1:
			continue
		for neighbour in neighbours:
			ancestors = {vertex}
			subtree1_vcnt = subtree_vertex_cnt(neighbour, ancestors, adj)
			ancestors = {neighbour}
			subtree2_vcnt = subtree_vertex_cnt(vertex, ancestors, adj)
			assert subtree1_vcnt > 0 and subtree2_vcnt > 0
			if subtree1_vcnt % 2 == 0 and subtree2_vcnt % 2 == 0:
				adj[vertex].remove(neighbour)
				adj[neighbour].remove(vertex)
				cnt += 1
				edge_removed = True
				break
print(cnt)


import collections
import random
import sys

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

class Graph(collections.defaultdict):

	def __init__(cls):
		super(Graph, cls).__init__(list)

	def connect(self, node1, node2):
		self[node1].append(node2)

	def disconnect(self, node1, node2):
		self[node1].remove(node2)

	def get_connected(self, node):
		for n in self[node]:
			yield n

	def subtree_size(self, node):
		total = 1
		for child in self.get_connected(node):
			total += self.subtree_size(child)
		return total

	def make_forest(self, root):
		if self.subtree_size(root) % 2:
			raise ValueError('input tree must contain an even number of vertices')
		return self._make_forest_recursive(root)

	def _make_forest_recursive(self, root):
		removed = 0
		for child in list(self.get_connected(root)):
			subtree_size = self.subtree_size(child)
			if not subtree_size % 2:
				self.disconnect(root, child)
				removed += 1
			removed += self._make_forest_recursive(child)
		return removed
graph = Graph()
(nvertices, nedges) = get_ints()
for nedge_index in range(nedges):
	(child, parent) = get_ints()
	graph.connect(parent, child)
root = min(graph.keys())
print(graph.make_forest(root))


import sys

def update_vertex(i, vertices):
	if not vertices[i][0]:
		return 0
	num_children = 0
	for d in vertices[i][0]:
		num_children += 1 + update_vertex(d, vertices)
	vertices[i][1] = num_children
	return num_children

def can_we_cut(i, vertices):
	if vertices[i][1] % 2 == 1:
		return True
	else:
		return False

def solve(n, edges):
	vertices = [None] + [[list(), 0] for _ in range(n)]
	for [l, r] in edges:
		vertices[l][0].append(r)
	update_vertex(1, vertices)
	result = -1
	for i in range(1, n + 1):
		if can_we_cut(i, vertices):
			result += 1
	return result

def main():
	[n, m] = [int(x) for x in input().split()]
	edges = [sorted([int(x) for x in input().split()]) for _ in range(m)]
	print(solve(n, edges))
	return 0
sys.exit(main())


tmp = str(input()).split()
nodes = int(tmp[0])
lines = int(tmp[1])
counts = [1] * nodes
edges = []
for k in range(0, lines):
	tmp = tmp = str(input()).split()
	edges.append(int(tmp[0]))
	edges.append(int(tmp[1]))
for i in range(lines * 2, 0, -2):
	tmp1 = edges[i - 2]
	tmp2 = edges[i - 1]
	counts[tmp2 - 1] = counts[tmp2 - 1] + counts[tmp1 - 1]
answer = 0
for j in range(1, nodes):
	if counts[j] % 2 == 0:
		answer = answer + 1
print(str(answer))


lists = [int(i) for i in input().split()]
N = lists[0]
M = lists[1]
root = 1
edge = []
nodes = {}
stack = []
stack_back = []
nodes_rem = []
children = []
children_check = []
for i in range(1, N + 1):
	nodes.update({i: []})
for i in range(0, N - 1):
	edge = [int(x) for x in input().split()]
	nodes[edge[0]].append(edge[1])
	nodes[edge[1]].append(edge[0])
stack.append(root)
count = 0
while count < N:
	point = stack[count]
	children = nodes[point]
	del nodes_rem[:]
	for i in children:
		if stack.count(i) != 0:
			nodes_rem.append(i)
		else:
			stack.append(i)
		i = i + 1
	for i in nodes_rem:
		nodes[point].remove(i)
	count = count + 1
for i in stack:
	stack_back.append(i)
while len(stack) != 0:
	del children[:]
	del children_check[:]
	ele = stack.pop()
	children = nodes[ele]
	children_check = nodes[ele]
	count = 0
	while count < len(children_check):
		x = children_check[count]
		children = children + nodes[x]
		count = count + 1
	nodes[ele] = nodes[ele] + children
count = 0
for i in stack_back:
	children = nodes[i]
	children = set(children)
	children = list(children)
	nodes.update({i: children})
flag = 0
for i in nodes:
	if len(nodes[i]) != 0 and len(nodes[i]) % 2 == 1:
		flag = flag + 1
print(flag - 1)


edges = []
(T, n) = tuple(map(int, input().split()))
for i in range(n):
	(c, p) = tuple(map(int, input().split()))
	edges.append((c, p))

def children(i):
	yield from (j for (j, k) in edges if i == k)

def clen(i):
	return 1 + sum((clen(j) for j in children(i)))

def detach(i, j, edges, roots):
	edges.remove((j, i))
counter = 0
print(len([(j, i) for j in range(0, T + 1) for i in children(j) if clen(i) % 2 == 0]))


import sys

def root(tree):
	return 1

def numNodes(tree, node):
	totalNodes = 1
	totalEdgesCut = 0
	children = tree[node]
	for child in children:
		(childNodes, childEdgesCut) = numNodes(tree, child)
		totalEdgesCut += childEdgesCut
		if childNodes % 2 == 0:
			totalEdgesCut += 1
		else:
			totalNodes += childNodes
	return (totalNodes, totalEdgesCut)
source = sys.stdin
(N, M) = tuple([int(s) for s in source.readline().split()])
tree = {i: [] for i in range(1, N + 1)}
for _ in range(M):
	(child, parent) = tuple([int(s) for s in source.readline().split()])
	tree[parent].append(child)
(nodes, edgesCut) = numNodes(tree, root(tree))
print(edgesCut)


(n, m) = input().split()
n = int(n)
m = int(m)
d = {}
numc = []
for z in range(m):
	(c, p) = input().split()
	c = int(c)
	p = int(p)
	d[c] = p
for x in range(1, n + 1):
	numc.append(0)
for x in range(1, n + 1):
	c = x
	while c in d:
		numc[d[c]] += 1
		c = d[c]
ans = -1
for i in numc:
	if i > 0 and i % 2 != 0:
		ans += 1
print(ans)


class Node:

	def __init__(self, id):
		self.id = id
		self.order = 1
		self.parent = None
		self.children = []

	def addChild(self, childNode):
		self.children.append(childNode)
		self.addOrder(childNode.order)
		childNode.addParent(self)

	def addParent(self, parentNode):
		self.parent = parentNode

	def addOrder(self, order):
		self.order += order
		if self.parent is not None:
			self.parent.addOrder(order)

	def printNodes(self):
		print('id: %d, order: %d' % (self.getId(), self.order))
		for child in self.children:
			child.printNodes()

	def getId(self):
		return self.id
(N, M) = list(map(int, input().split(' ')))
nodeArray = [Node(1)]
for i in range(1, M + 1):
	(ui, vi) = list(map(int, input().split(' ')))
	uiNode = Node(i + 1)
	nodeArray.append(uiNode)
	nodeArray[vi - 1].addChild(uiNode)
count = 0
for node in nodeArray[1:]:
	if node.order % 2 == 0:
		count += 1
print(count)