Competitions
ADA Training CP
Even Tree
You are given a tree (a simple connected graph without 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.
Input data
The first line contains two integers n (2 ≤ n ≤ 100, n is even) and m - the number of nodes and edges. The next m lines contain two integers which specify the nodes connected by an edge of the tree. The root of the tree is node 1.
Output data
Print the maximum number of removed edges.
Examples
Input example #1
10 9 2 1 3 1 4 3 5 2 6 1 7 2 8 6 9 8 10 8
Output example #1
2