검술 학교에 \(N\)명의 학생이 있다. 이들 중 일부 쌍은 서로 대련 상대로 합이 잘 맞아 함께 한 조를 이룰 수 있다. 어떤 두 학생이 한 조를 이룰 수 있는지는 \(M\)개의 호환 쌍 목록으로 주어진다.

각 학생은 최대 한 조에만 속할 수 있고, 한 조는 정확히 두 명의 호환되는 학생으로 구성된다. 가능한 한 많은 조를 동시에 만들고자 할 때, 만들 수 있는 조의 최대 개수를 구하라.

호환 관계에는 어떤 특별한 구조도 가정할 수 없다. 예를 들어 학생들을 두 진영으로 나누어 같은 진영끼리는 절대 호환되지 않게 만드는 것이 불가능할 수도 있다.

\(1 \le N \le 500\)

\(0 \le M \le \dfrac{N(N-1)}{2}\)

첫 줄에 학생 수 \(N\)과 호환 쌍의 수 \(M\)이 주어진다.

이어서 \(M\)개의 줄에 각각 두 정수 \(u\), \(v\)가 주어지며, 이는 학생 \(u\)와 \(v\)가 한 조를 이룰 수 있음을 뜻한다 (\(1 \le u, v \le N\), \(u \neq v\)). 같은 쌍이 두 번 주어지지 않는다.

만들 수 있는 조의 최대 개수를 한 줄에 출력한다.

riseoj 작성

출처 Original