Interviewstreet Challenge: Even Tree

Problem

https://www.interviewstreet.com/challenges/dashboard/#problem/4fffc24df25cd

You are given a tree (a simple connected graph with no cycles).You have to remove as many edges from the tree as possible to obtain a forest with the condition that : Each connected component of the forest contains even number of vertices

Your task is to calculate the number of removed edges in such a forest.

Input:
The first line of input contains two integers N and M. N is the number of vertices and M is the number of edges. 2 <= N <= 100.
Next M lines contains two integers u_i and v_i which specifies an edge of the tree. (1-based index)

Output:
Print a single integer which is the answer

Sample Input 

10 9

2 1

3 1

4 3

5 2

6 1

7 2

8 6

9 8

10 8

Sample Output :

2

Explanation : On removing the edges (1, 3) and (1, 6), we can get the desired result.

Original tree:


Decomposed tree:

Note: The tree in the input will be such that it can always be decomposed into components containing even number of nodes. 

Analysis

All Java Solutions on the InterviewStreet needs to run in 5 seconds with 256 MB maximum RAM available. So that means our solution can never be "Brute-Force" or O(n^2). Same applies to the space complexity.

Well this is an interesting problem. Initially it appears to be a problem of n-ary trees. But to build a tree and perform the decomposition on the trees, it is time consuming. So I approached it with a Map approach. And well all my 10 testcases took around 1 sec only.
Create a map with parent as key and list of all its children. Now once this map is created, then take the root. Get each of its children from the list. So we have 1 as the node and 2, 3, 6 as children. So take 2. Check if the total number of nodes under it are even or odd (I am using a recursive call here to get the count.) In this case we have only two nodes - 7 and 5 (even number of nodes). So we cannot remove the link 1-3. Since that leaves with a subtree with 3-nodes (2, 7 and 5) which is not even number. So do not increment the count. However remove 2 from the list of 1's children and add 7 and 5 to the list. 
Now take 6, it has 3 children (8, 9 and 10). So the link 1-6 can be removed. Increment counter, remove 6, add 8, 9 and 10 to the list.
The next entries 7, 5, and 4 have no children. Continue to 8. It has 2 children, hence cannot remove.

Now take the next element in the list - it is 3. It has only 1 child (odd number). So that means we can break 1-3 link. Increase the counter, remove 3 and add 4 to the list.

Solution