In this program you will read a file specifying a graph as a list of edges and output the same graph as an adjacency list such that the list of neighbors of each vertex is in increasing order. The input file simply lists the edges in arbitrary order as pairs of vertices, with each edge on a separate line. The vertices are numbered in order from 1 to the total number of vertices. You algorithm should run in linear time. For example the input of the complete on 4 vertices may look like:

1 2

2 3

3 1

4 1

2 4

4 3

and the corresponding output lists is:

1: 2 3 4

2: 1 3 4

3: 1 2 4

4: 1 2 3

The first line in the output lists the neighbors of vertex 1, the second line lists the neighbors of vertex 2, and so on.

Note that isolated vertices may not appear in the input. If v is an isolated vertex then the output line for such vertex is:

v:

You can assume that the largest vertex number that appear in the input is the number of vertices.

In a comment at the top of your program explain why you algorithm runs in linear time (time proportional to V+E).

Note: Your program must be written in C and must be able to be compiled using the gcc compiler!