Problem two:
Battlefield

Write a program which could be part of a Battlefield Command and Control System. Your program must group tanks. A group is defined as a set of tanks which are in close proximity to each other. "Close proximity" is figured out via secret algorithms that we are not allowed to tell you about. Luckily though, this proximity detection software outputs pairs of tanks that are known to be close. You need only group these. The groups are to be ranked in descending order. The order is based on size of the groups. The largest group is the best target.

You are given ID numbers of n tanks, numbered 1,...,n. You are also given information on the proximity of one tank to another tank.

Input:

The first line specifies the number of tanks. Each subsequent line specifies tanks, in pairs, which are in close proximity to each other.

Output:

Print the groups of tanks, from largest group to smallest group. Within each group, specify each tank in ascending ID number order. In the case where more than one group has the same size, list the group having the smallest ID number first. For example:

Input:
  15
  1  15
  1  2
  2  13
  3  15
  5  6
  5  4
  7  6
  12 11
  10 11
  14 12
  8  14
  7  4

Output: 
  Group 1:  8  9  10  11 12  14
  Group 2:  1  2  3  13  15
  Group 3:  4  5  6  7
  Group 4:  9

Doug Lea

Last modified: Fri Oct 15 14:27:53 EDT 1999

Problem two: Battlefield

Input:

Output:

Problem two:
Battlefield