【CF簡(jiǎn)介】

提交鏈接：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個(gè)朋友，m個(gè)敵對(duì)關(guān)系。敵對(duì)關(guān)系是相互的，即a和b是敵對(duì)的，那么b和a也是敵對(duì)的，具有敵對(duì)關(guān)系的兩個(gè)人不能在一個(gè)小組，一個(gè)人最多只有兩個(gè)敵對(duì)對(duì)象?，F(xiàn)在要求將所有人分成兩個(gè)小組，使得兩組人數(shù)相同，且內(nèi)部不具備敵對(duì)關(guān)系，且做板凳（即未被選中的人的數(shù)量盡量少）。

解題：

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

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

代碼：

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