Training Site

Connected Components

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 64 megabytes
Time limit: 2.0 seconds

Read in a undirected graph which has been described as a list of edges and then output the connected components of the graph.

Input format

Each vertex will be represented as a number from 0 to n-1 for n vertices.
The first line of input will state how many vertices are in the graph
Each subsequent line will consist of pairs of numbers each describing an edge. The first number in the pair describes the vertex from where the edge originates and the second number states the vertex where the edge leads to. The list will end in a -1 -1 pair which is not to be included as an edge.

Output format

Output on separate lines the vertices, (sorted and separated by spaces) in each of the connected components of the graph. Label the components numerically starting at 1.

The vertices of each component should be sorted in increasing order. The components should be ordered by their lowest vertex.

• Sample Input 1

6
3 1
5 0
2 0
1 4
2 5
4 3
-1 -1


Sample Output 1

1: 0 2 5
2: 1 3 4