화학 약품 옮기기
시간 제한1초메모리 제한1024 MB
두 실험실이 각각 n종의 화학물질을 보관하며, 금지된 A-B 쌍을 피하면서 최대 n/2쌍까지 서로 교환할 때 옮길 수 있는 화학물질 종류의 최댓값을 구한다.
문제
한 회사가 연구실에 보관된 화학 약품을 옮기기로 했다. 이 회사에는 두 개의 연구실이 있고(각각 A 연구실, B 연구실이라 하자), 각 연구실에는 n가지 종류의 화학 약품이 보관되어 있다. 연구실 크기 문제로 각 연구실에는 n가지 화학 약품만 보관할 수 있으므로, A 연구실의 화학 약품 일부를 같은 개수의 B 연구실 화학 약품과 바꾸어야 한다.
화학 약품이 보관된 연구실을 바꾸면 회사의 기밀이 새 나가는 것을 막는 효과가 있으므로, 회사는 최대한 많은 화학 약품을 옮기려고 한다. 그런데 일부 화학 약품은 같은 연구실에 보관하면 안전사고가 발생할 위험이 있다. 또한 약품을 옮기는 과정에서도 안전사고가 발생할 수 있으므로, n/2 종류를 초과해서 화학 약품을 바꾸지 않기로 했다.
같은 연구실에 보관할 수 없는 화학 약품 쌍의 목록이 주어졌을 때, 옮길 수 있는 화학 약품의 최대 종류수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 두 정수 n(1 ≤ n ≤ 200), m(0 ≤ m ≤ n2)이 주어진다. m은 같은 연구실에 보관할 수 없는 약품 쌍의 개수이다. 다음 m개의 줄에는 두 정수 a, b(1 ≤ a, b ≤ n)가 주어진다. 이는 A 연구실에 보관된 a번 약품을 B 연구실의 b번 약품과 함께 보관할 수 없다는 뜻이다.
출력
첫째 줄에 옮길 수 있는 화학 약품의 최대 종류수를 출력한다.
힌트
A 연구실의 6, 7, 8번 화학 약품과 B 연구실의 6, 7, 8번 화학 약품을 바꾸면 된다. 이 예에서 두 연구실에 있는 약품의 번호가 우연히 같았을 뿐이며, 번호가 꼭 일치해야 하는 것은 아니다. 개수만 맞으면 된다.