AndWinComp

All submissions for this problem are available.
One day a teacher give some task to students to build applications for mobile phones. Some students want to build the apps for android and others for windows phone. So the teacher decided to split them into teams, the teams must have an equal number of students.
We know that this group of students 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 idle in the class.
Determine the minimum number of students you will have to make them sit idle in order to form the two teams in the described manner and begin the competition at last.
Input
The first line of the input contains an integer T, the number of test cases.T test cases follow. The first line of each test case contains two space integers n and m — 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 ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — 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
For each test case, in new line, print a single integer — the minimum number of students you will have to send to the bench in order to start the game.
Constraints
1<=T<=1000
2<=n<=100
1<=m<=100
Example
Input: 1 5 4 1 2 5 3 2 4 1 4 Output: 1
Author:  prog_iitmandi 
Tags  prog_iitmandi 
Date Added:  24102012 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, GO, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 