HACKERRANK   --

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 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

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

Original tree:

Decomposed tree:

       ########### editorial###############

 in this problem we need to count no of different pair of disconnected components we can form   such that both disconnected component must contain even no of nodes ..(pair because adding even no in any no do not change its nature (even ,or odd));;;

##########  code #####################

#include<iostream>

using namespace std;

#include<bits/stdc++.h>

list<int >li[500];

int has[500][500];

int vis[10001];

int c=0;

void  bfs(int a,int b)///  count no of nodes after disconnecting grah byy

                            //deleting edge b/w node aand node b

 {

  queue<int>q;

  q.push(a);

  vis[a]=1;

  int start;

   int cou=0;

   while(!q.empty())

    {

    start=q.front();

    q.pop();

     cou++;

   

     list<int>:: iterator it;

     for(it=li[start].begin();it!=li[start].end();it++)

      {

      if(vis[*it]==0 && *it!=b)

      {

      vis[*it]=1;

      q.push(*it);

      }

     

      }

    }

    int cou1=0;

    start=b;

    q.push(b);

    vis[b]=1;

    while(!q.empty())

     {

       start=q.front();

       q.pop();

       cou1++;

       

       list<int> ::iterator it;

        for(it=li[start].begin();it!=li[start].end();it++)

         {

          if(vis[*it]==0  && *it!=a )

          {

 vis[*it]=1;

 q.push(*it);

           

          }

         }

     }

     

if(cou1%2==0 && cou%2==0) c++;  // if both dissconected                                                                        //components  contain even                                                                // no  of nodes then increase

                                                        // count 

                                                           

                                                           

                                                                         

 }

int main()

 {

  int n,m;

  cin>>n>>m;

   for(int i=1;i<=m;i++)

    {

     int a,b;

      cin>>a>>b;

       li[a].push_back(b);

       li[b].push_back(a);

       has[a][b]=1;// has contain is there any edge b/w aandb;

        has[b][a]=1;

    }

    

    for(int i=1;i<=n;i++)

     {

      for(int j=1;j<=n;j++)

       {

         if(i!=j && has[i][j]  && has[j][i])// means there is a                                                                                   edge is b/w i,j

          {

            for(int i=0;i<=n;i++) vis[i]=0;

           has[i][j]=0;//unhash 

           has[j][i]=0;// unhash

              bfs(i,j);

              

          }

       }

     }

     cout<<c<<endl;

 

 }