package algorithms.graph_theory;

import java.util.Arrays;
import java.util.Scanner;

/*
 * Problem Statement: 
 * 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 should contain an
 * even number of vertices.
 * 
 * To accomplish this, you will remove some edges from the tree. Find out the
 * number of removed edges.
 * 
 * Input Format:
 * The first line of input contains two integers N and M. N is the number of
 * vertices and M is the number of edges.
 * The next M lines contain two integers ui and vi which specifies an edge of
 * the tree. (1-based index)
 * 
 * Output Format:
 * Print the answer, a single integer.
 * 
 * Constraints:
 * 2 <= N <= 100.
 * 
 * Note: The tree in the input will be such that it can always be decomposed
 * into components containing even number of nodes.
 * 
 * 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
 */
public class EvenTree {

    public static void main(String[] args) {
        
        int tree[];
        int count[];
               
        Scanner sc = new Scanner(System.in);
               
        int numVertices = sc.nextInt();
        int numEdges = sc.nextInt();
               
        tree = new int[numVertices];
        count = new int[numVertices];
        Arrays.fill(count, 1);
               
        for (int i = 0; i < numEdges; i++) {
                        
            int childVert = sc.nextInt();
            int parentVert = sc.nextInt();
                   
            tree[childVert - 1] = parentVert;
                   
            count[parentVert - 1] += count[childVert - 1];
                   
            int root = tree[parentVert - 1];
                   
            while(root != 0) {
                count[root - 1] += count[childVert - 1];
                root = tree[root - 1];
            }
        }
        sc.close();
               
        int counter = -1;
                
        for(int i = 0; i < numEdges; i++) {
                        
            if(count[i] % 2 == 0) {
                counter++;
            }
                   
        }
        System.out.println(counter);
    }
}
Add EvenTree