시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2 2 2 100.000%

문제

The big day has finally arrived: today you are going to form groups of two in which you will do the end-of-the-year project. When you arrive at school, you learn that the teacher of the other class is sick, and that your teacher, Mr. B.A.P. Cee, will also have to make groups for the other class. Mr. B.A.P. Cee is a smart guy and realizes that he can use these unfortunate circumstances to his advantage.

Ending up with groups of one should be avoided at all cost, so mixing the students of the two classes may avoid this situation. However, while it is easy to pair up two students from the same class, it is more difficult to match up students from different classes. Throughout the years there has been a lot of rivalry between the two groups, and many students dislike students in the other class. Mr. B.A.P. Cee knows which pairs of students will result in a fight and a failed project.

You are given a list of pairs of students who cannot work together. How many disjoint groups of two can Mr. B.A.P. Cee make that will not result in a failed project?

입력

The input consists of:

  • A line with two integers $n$ ($1 \leq n \leq 10^5$), the number of students, and $m$ (${0\leq m\leq 2\cdot10^5}$), the number of pairs of students who cannot work together.
  • $m$ lines, each with two distinct integers $i$ and $j$ ($1\leq i, j\leq n$, $i \neq j$), giving a pair of students who cannot work together.

Students are identified by the numbers $1$ through $n$. It is guaranteed that it is possible to split the students into two classes in such a way that all students from the same class get along.

출력

Output the number of pairs of students Mr. B.A.P. Cee can make without making any pair of students who cannot work together.

예제 입력 1

3 2
1 2
3 1

예제 출력 1

1

예제 입력 2

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

예제 출력 2

2

예제 입력 3

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

예제 출력 3

3

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2020 Preliminaries G번

  • 문제를 만든 사람: Ragnar Groot Koerkamp, Timon Knigge