채널 배정

라디오 방송국이 아주 넓은 지역에 방송을 할 때, 모든 수신기가 강한 신호를 받을 수 있도록 신호를 다시 송출하는 중계기(repeater)를 사용한다. 이때 서로 가까운 중계기들이 간섭을 일으키지 않도록 각 중계기가 사용하는 채널을 신중하게 정해야 한다. 인접한 두 중계기가 서로 다른 채널을 사용하면 이 조건이 만족된다.

주파수 스펙트럼은 귀중한 자원이므로, 중계기 네트워크가 사용하는 채널의 수는 최대한 적어야 한다. 중계기 네트워크에 대한 설명을 읽고 필요한 최소 채널 수를 구하는 프로그램을 작성하라.

입력은 여러 개의 중계기 네트워크 지도로 이루어진다. 각 지도는 중계기의 수가 적힌 줄로 시작한다. 이 수는 1 이상 26 이하이며, 중계기는 A부터 시작하는 연속된 대문자로 이름이 붙는다. 예를 들어 중계기가 10개이면 이름은 A, B, C, …, I, J이다. 중계기 수가 0인 지도는 입력의 끝을 의미한다.

중계기 수 다음에는 인접 관계 목록이 이어지며, 알파벳 순서대로 중계기마다 한 줄씩 주어진다. 각 줄은 다음과 같은 형태이다.

A:BCDH

이는 중계기 B, C, D, H가 중계기 A와 인접함을 뜻한다. 첫 번째 줄은 A와 인접한 중계기를, 두 번째 줄은 B와 인접한 중계기를 나타내며, 나머지도 같은 방식이다. 어떤 중계기와도 인접하지 않은 중계기의 줄은 다음과 같은 형태이다.

A:

인접 관계는 대칭이다. 즉 A가 B와 인접하면 B도 A와 인접한다. 또한 중계기들은 평면 위에 놓여 있으므로, 인접 관계로 이루어진 그래프는 평면 그래프이다(어떤 두 변도 서로 교차하지 않는다).

중계기 수가 0인 마지막 지도를 제외한 각 지도에 대해, 인접한 중계기끼리 간섭하지 않도록 하는 데 필요한 최소 채널 수를 한 줄에 출력한다. 출력 형식은 예제 출력과 정확히 같아야 한다. 채널이 정확히 1개 필요하면 단수형 channel을, 그렇지 않으면 복수형 channels을 사용한다.