Training Site
Sideways banner

Adjacency List Exercise

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 100 megabytes
Time limit: 1.0 seconds

Read in a directed graph which has been described as a list of edges and output the sorted adjacency list for the graph as shown.

Input format

Each vertex (or node) will be represented as a number from 0 to n-1 for n vertices (1 < n <= 1000). 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

Each vertex shall be printed at the start of a new line, followed by a colon : and a sorted, space separated, list of adjacent vertices

Sample Input

3
0 1
1 0
1 2
0 2
2 0
-1 -1

Sample Output

0: 1 2
1: 0 2
2: 0

Optional Exercise (do not submit)

Modify your program to interpret the data as describing an undirected graph