별자리

어느 날 밤, 넓은 들판에서 야영을 하던 빅 에드(Big Ed)는 별을 바라보고 있었다. 에드는 별자리를 배운 적이 없었지만, 별들을 무리 지어 보는 것도 나름 의미 있는 일이라고 생각했다. 그는 다음과 같은 간단한 규칙에 따라 별을 묶기로 했다.

• 모든 별은 자신과 가장 가까운 별과 같은 별자리에 속한다.
• 가장 가까운 별이 여러 개라면, 그 별과 가장 가까운 모든 별이 같은 별자리에 속한다.
• A가 B와 같은 별자리에 속하면, B도 A와 같은 별자리에 속한다.
• A가 B와 같은 별자리에 속하고 B가 C와 같은 별자리에 속하면, A도 C와 같은 별자리에 속한다.

여기서 "가까움"은 두 별의 좌표 사이의 일반적인 유클리드 거리로 측정한다.

예를 들어 하늘이 다음과 같이 보인다면,

별자리는 3개이다: {1, 2, 3, 4, 5}, {6, 7, 8}, {9, 10}.

입력은 여러 개의 하늘 설명으로 이루어진다. 각 설명은 별의 개수를 나타내는 정수 $n$ ($0 < n \le 500$)이 적힌 줄로 시작한다.

이어지는 $n$개의 줄에는 각 별의 좌표가 두 정수 $x$, $y$ ($0 \le x, y \le 1000$)로 주어진다.

$n = 0$인 줄은 입력의 끝을 의미한다.

각 하늘 설명마다 다음 형식으로 한 줄을 출력한다.

Sky s contains c constellations.

여기서 $s$는 하늘 설명의 번호(1부터 시작)이고 $c$는 별자리의 개수이다.