Problem 1011: Universe in the Cupboard

(ACM S.E. U.S.A. Regional 2003, problem 11)

Description

Little Omri has been playing with his magic cupboard again and has accidentally created a parallel universe, complete with stars, planets, people and everything. The people of the planet Parallearth gazed up at the sky on their first night of existence, and noticed that the stars appear to be in groups, which they chose to call constellations. Before the big vote to choose names for the constellations, they want to know how many there are, and that's where you come in. <> The Parallearthlings have taken a photograph of the night sky, which renders all the bright stars in a rectangular frame. They then put a regular grid on the photograph so they could determine the coordinates of all of the stars. These coordinates have been written down in a list. Your program should process that list of two-dimensional coordinates and print out how many constellations can be made from the visible stars.

There are very simple rules for constructing constellations:

Every star is in the same constellation as its closest neighbor.
If a star doesn.t have a unique closest neighbor.i.e. two or more neighbors are equally close and no others are closer.then it is in the same constellation as all of those closest neighbors.
If A is in the same constellation as B, then B is in the same constellation as A.
If A is in the same constellation as B, and B is in the same constellation as C, then A is in the same constellation as C.

For example, if the following were the picture of the night sky:

The first constellation consists of

1, and

1. Stars

1 and

1 are in the same constellation because

1 is the closest star to

1 (i.e., by rule 1). Since

1 has three closest neighbors (

1, and

1), all of these are in the same constellation as

1 (by rule 2). Similarly,

2 is the closest neighbor of

2, and

2 is the closest neighbor to

2, so they are all in the same constellation (by rule 4). Finally,

3 and

3 are in a third constellation.

Input Format

The input to the program will consist of a sequence of universe specifications. Each begins with a single line containing a single integer n (0 < n <= 1000), the number of stars in that universe. There then follow n lines, each containing two integers x and y (0 <= x,y <= 9999), which are the coordinates of a star on the official photograph.

The last universe specification has n=0, and should not be processed.

Output Format

For each universe specification, your program should print a single line that looks like:
Universe n contains c constellations
where n is replaced by the universe number (the first is 1), and c is replaced by the number of constellations.

Sample Input

Sample Output

Universe 1 contains 3 constellations
Universe 2 contains 1 constellations