codeforces 216B-Forming Teams

Description

One day n students come to the stadium. They want to play football, and for that they need to split into teams, the teams must have an equal number of people.

We know that this group of people has archenemies. Each student has at most two archenemies. Besides, if student A is an archenemy to student B, then student B is an archenemy to student A.

The students want to split so as no two archenemies were in one team. If splitting in the required manner is impossible, some students will have to sit on the bench.

Determine the minimum number of students you will have to send to the bench in order to form the two teams in the described manner and begin the game at last.

Input

The first line contains two integers n and m (2?≤?n?≤?100, 1?≤?m?≤?100) — the number of students and the number of pairs of archenemies correspondingly.

Next m lines describe enmity between students. Each enmity is described as two numbers a_i and b_i (1?≤?a_i,?b_i?≤?n, a_i?≠?b_i) — the indexes of the students who are enemies to each other. Each enmity occurs in the list exactly once. It is guaranteed that each student has no more than two archenemies.

You can consider the students indexed in some manner with distinct integers from 1 to n.

Output

Print a single integer — the minimum number of students you will have to send to the bench in order to start the game.

Sample Input

5 4
1 2
2 4
5 3
1 4

1

6 2
1 4
3 4

0

6 6
1 2
2 3
3 1
4 5
5 6
6 4

2

思路：題目大意就是，要組織足球賽，首先其中的隊員都會有仇人，所以他們不能夠在同一組，每個人的仇人的個數不超過兩個，如果A與B是仇人，那麼B與A也是仇人，給定仇人的序列，讓你判斷需要剔除的最少人數以使足球賽能夠進行。

並查集的題目，用root數組將能夠成為一組的人並在一起，使用sex數組記錄每個人的敵人，具體見代碼（思路可參照本博客中並查集的A bug‘s life！）。

代碼：

#include 
#include 
#include 
using namespace std;
int root[110],sex[110];
int n,m;
void chu()
{
    for(int i=0;i<=n;i++)
        root[i]=i;
        memset(sex,0,sizeof(sex));
}
int look(int a)
{
    if(a!=root[a])
        a=look(root[a]);
    return a;
}
void _union(int a,int b)
{
    a=look(a);
    b=look(b);
    if(a!=b) root[a]=b;
}
int main()
{
     while(scanf("%d%d",&n,&m)!=-1)
     {
         int x,y;
         int i,ans=0;
         chu();
         for(i=0;i