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.
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.
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.
Input: 1 5 4 1 2 5 3 2 4 1 4 Output: 1
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, GO, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.