캠퍼스의 서로 다른 종교
면접 대비시간 제한1초메모리 제한128 MB
같은 종교를 믿는 학생 쌍 정보가 주어질 때, 유니온-파인드로 가능한 최대 종교 수를 여러 테스트케이스에 대해 구합니다.
문제
한 대학교에 n명의 학생이 있다. 이 학교의 학생들이 믿는 종교가 최대 몇 가지인지 알고 싶지만, 모든 학생에게 직접 물어보는 것은 어렵고 학생들이 자신의 믿음을 밝히기 꺼릴 수도 있다.
대신 m쌍의 학생에 대해 두 학생이 같은 종교를 믿는다는 사실만 주어진다. 이 정보만으로 각 학생의 종교를 정확히 알 수는 없지만, 학교에 존재할 수 있는 서로 다른 종교 수의 최댓값은 구할 수 있다.
각 학생은 많아야 하나의 종교만 믿는다고 가정한다. 학생 수는 0 < n <= 50000이고, 관계 수는 0 <= m <= n(n-1)/2이다.
입력
입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 정수 n과 m이 주어진다.
이어지는 m개의 줄에는 정수 i와 j가 주어지며, 학생 i와 학생 j가 같은 종교를 믿는다는 뜻이다. 학생 번호는 1부터 n까지이다.
n = 0이고 m = 0인 줄이 나오면 입력이 끝난다.
출력
각 테스트 케이스마다 한 줄에 Case x: y 형식으로 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 주어진 정보와 모순되지 않게 학생들이 믿을 수 있는 서로 다른 종교 수의 최댓값이다.