모둠 프로젝트

시간 제한2초메모리 제한512 MB

요약

충돌 그래프가 이분 그래프임이 보장될 때, 서로 충돌하지 않는 두 학생씩 짝지은 최대 쌍의 개수를 구한다.

난이도: 보통10점 중 7점
유형: 그래프, 그리디, 수학, 조합론
정답자: 아직 제출이 없습니다

문제

드디어 그날이 왔다. 오늘은 둘씩 모둠을 이루어 학기말 프로젝트를 진행한다. 학교에 도착해 보니 옆 반 선생님이 아프고, 담당 선생님인 B.A.P. Cee 선생님이 옆 반의 모둠까지 짜야 한다는 사실을 알게 된다. B.A.P. Cee 선생님은 영리해서 이 불운한 상황을 자기에게 유리하게 이용할 수 있다는 것을 깨닫는다.

한 명짜리 모둠이 생기는 일은 무슨 수를 써서라도 피해야 하므로, 두 반 학생을 섞으면 이런 상황을 피할 수 있다. 하지만 같은 반 학생 둘을 짝지어 주는 것은 쉽지만, 서로 다른 반 학생을 짝지어 주는 것은 더 어렵다. 오랫동안 두 반 사이에 라이벌 관계가 있어서 다른 반 학생을 싫어하는 학생이 많다. B.A.P. Cee 선생님은 어떤 학생 쌍이 싸움과 프로젝트 실패로 이어지는지 알고 있다.

함께 일할 수 없는 학생 쌍의 목록이 주어진다. B.A.P. Cee 선생님이 프로젝트 실패로 이어지지 않도록 만들 수 있는, 서로 겹치지 않는 둘씩의 모둠은 몇 개인가?

입력

입력은 다음과 같다.

학생 수 $n$ ( $1 \leq n \leq 10^5$ )과 함께 일할 수 없는 학생 쌍의 수 $m$ ( ${0\leq m\leq 2\cdot10^5}$ )이 주어지는 한 줄.
함께 일할 수 없는 학생 쌍을 나타내는 서로 다른 두 정수 $i$ 와 $j$ ( $1\leq i, j\leq n$ , $i \neq j$ )가 주어지는 $m$ 개의 줄.

학생은 $1$ 부터 $n$ 까지의 번호로 구별된다. 같은 반 학생끼리는 모두 사이가 좋도록 학생을 두 반으로 나눌 수 있음이 보장된다.

출력

B.A.P. Cee 선생님이 함께 일할 수 없는 학생 쌍을 하나도 만들지 않고 구성할 수 있는 학생 쌍의 수를 출력한다.

예제3

예제 1
입력
```
3 2
1 2
3 1
```
예상 출력
```
1
```
예제 2
입력
```
5 6
1 4
2 4
3 4
1 5
2 5
3 5
```
예상 출력
```
2
```
예제 3
입력
```
6 6
1 4
2 5
3 6
1 5
3 5
2 6
```
예상 출력
```
3
```