지도 색칠하기

당신은 이제부터 탐험할 신비한 세계의 지도를 손에 넣었다. 지도에는 국경이 복잡하게 얽힌 여러 나라가 그려져 있고, 탐험 예정 지역 전체가 담겨 있다. 그러나 한 가지 잉크 색으로만 그려져 있어서 어느 영역이 어느 나라에 속하는지 한눈에 알아보기 어렵다. 그래서 출발 전에 지도에 색을 칠하기로 했다.

각 나라는 하나 이상의 영토로 이루어지며, 각 영토는 단순 다각형 모양이다. 한 나라의 영토들은 서로 붙어 있지 않을 수도 있으므로, 한 나라가 서로 떨어진 여러 영토를 가질 수 있다. 같은 나라에 속한 모든 영토는 반드시 같은 색으로 칠해야 한다. 서로 다른 두 나라는 같은 색을 써도 되지만, 인접한 두 나라는 서로 다른 색으로 칠해야 한다. 두 나라는 각자의 영토 중 어느 것이라도 길이가 0이 아닌 경계를 공유하면 인접한 것으로 본다. 한 점에서만 만나는 영토들은 경계를 공유하는 것으로 치지 않는다.

이 규칙에 따라 지도를 칠하는 데 필요한 최소 색의 개수를 구하는 프로그램을 작성하여라.

입력은 여러 개의 지도로 이루어진다. 각 지도는 영토의 총 개수 $n$ 이 적힌 줄로 시작한다. $n$ 은 $n \le 100$ 인 양의 정수이다. 그 뒤에 $n$ 개의 영토 자료가 이어진다.

꼭짓점이 $m$ 개인 영토는 다음 형식으로 주어진다.

String
x1 y1
x2 y2
...
xm ym
-1

String 은 그 영토가 속한 나라의 이름으로, 영숫자로 이루어진 문자열이며 길이는 1자 이상 20자 이하이다. 한 나라에 영토가 여럿이면 각 영토마다 같은 이름이 나타난다.

나머지 줄은 영토의 꼭짓점을 나타낸다. 각 꼭짓점 줄에는 음이 아닌 두 정수, 곧 $x$ 좌표와 $y$ 좌표가 공백 하나로 구분되어 있으며, 어느 좌표도 1000을 넘지 않는다. 영토의 변은 이웃한 두 꼭짓점을 잇고, 마지막 꼭짓점과 첫 꼭짓점을 이어 얻는다. -1 만 있는 줄이 꼭짓점 목록의 끝을 나타낸다. 꼭짓점의 개수는 $m \le 100$ 을 만족한다.

모든 다각형은 단순하며(경계가 스스로 교차하거나 맞닿지 않음), 서로 다른 두 다각형은 넓이가 0이 아닌 영역을 공유하지 않는다고 가정해도 좋다. 한 지도에 들어 있는 나라의 수는 10을 넘지 않는다.

입력의 끝은 0 하나만 있는 줄로 나타낸다.

각 지도마다, 주어진 규칙에 따라 칠하는 데 필요한 최소 색의 개수를 한 줄에 출력한다.