Even Tree

 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

 

import java.util.*;

 public class Solution{

    public static void main(String[] args){

        Scanner in = new Scanner(System.in);

        int N = in.nextInt();

        int M = in.nextInt();

        Integer[][] edges = new Integer[M][2];

        for(int i=0;i<M;i++){

            edges[i][0] = in.nextInt();

            edges[i][1] = in.nextInt();

            if(edges[i][0]>edges[i][1]){

                int tmp = edges[i][0];

                edges[i][0] = edges[i][1];

                edges[i][1] = tmp;

            }

        }

        Arrays.sort(edges,new Comparator<Integer[]>(){

            @Override

            public int compare(Integer[] int1, Integer[] int2){

                Integer v1 = int1[0];

                Integer v2 = int2[0];

                return v1.compareTo(v2);

            }

        });

        int[] count = new int[N];

        count[0] = N;

        for(int i=1;i<N;i++){

            ArrayList<Integer> a = new ArrayList<Integer>();

            a.add(i+1);

            int j = 0;

            while(j<a.size()){

                for(int m=j;m<M;m++){

                    if(edges[m][0]==a.get(j)){

                        if(!a.contains(edges[m][1])){

                            a.add(edges[m][1]);

                        }

                    }

                }

                j++;

            }

            count[i] = a.size();

        }

        int remove = 0;

        for(int c:count){

            if(c%2==0)

                remove++;

        }

        System.out.println(remove-1);                  

    }

}