【打CF，學算法——三星級】CodeForces 216B Forming Teams （圖論）

【CF簡介】

提交鏈接：CF 216B

題面：

B. Forming Teams time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

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.

Examples Input

5 4
1 2
2 4
5 3
1 4

Output

1

Input

6 2
1 4
3 4

Output

0

Input

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

Output

2

--------------------------------------------------------------------------------------做完再看------------------------------------------------------------------------------------------------------------------------------

題意：

??? 給定n個朋友，m個敵對關系。敵對關系是相互的，即a和b是敵對的，那么b和a也是敵對的，具有敵對關系的兩個人不能在一個小組，一個人最多只有兩個敵對對象?，F(xiàn)在要求將所有人分成兩個小組，使得兩組人數(shù)相同，且內部不具備敵對關系，且做板凳（即未被選中的人的數(shù)量盡量少）。

解題：

??? 將題目給定的敵對關系構造成圖，可以發(fā)現(xiàn)，聯(lián)通塊要么是環(huán)，要么是鏈，要么就是孤立點（因為一個點最多只有2的度數(shù)）。分析可以比較容易得出，奇數(shù)長度的環(huán)，必須犧牲一個人做板凳，因為選出的len-1人分為兩個小組，必有一人與兩個小組的人都存在敵對關系，故而找奇環(huán)，發(fā)現(xiàn)則做板凳人數(shù)數(shù)量加一。如果是鏈，可以i,i+1分別分配給兩個小組，就不會出現(xiàn)敵對關系，但奇數(shù)鏈會損失一個，但不同鏈之間無敵對關系，因此可以鏈接所有鏈，最終鏈長度為奇數(shù)，則損失一個。

???? 注意：找奇環(huán)的過程，開始寫錯了，應該是計算一個聯(lián)通塊上的總度數(shù)，并記錄是否出現(xiàn)了度數(shù)為1或者為0的點，沒有則判定為環(huán)，奇環(huán)的總度數(shù)/2是奇數(shù)，可以通過這點判斷奇環(huán)。

代碼：

#include 
#include 
#include 
#include 
#include 
#include