Adjacency List - Graph Representation

One of the most popular ways of representing graphs is with adjacency lists. An adjacency list is a way of representing a graph as an array of lists. Each element of the array represents a vertex in the graph, and the list associated with that vertex contains the vertices that are adjacent to it.
Given the directed graph in the picture, we can obtain its adjacency list:
g = [
  [],        # We skip vertex 0
  [2, 4],    # Vertex 1
  [5],       # Vertex 2
  [2],       # Vertex 3
  [],        # Vertex 4
  [6, 8],    # Vertex 5
  [4, 7],    # Vertex 6
  [8],       # Vertex 7
  [5],       # Vertex 8
]
Directed graph with 8 edges and 10 edges. Notice that vertices 5 and 8 have a bidirectional connection.
Directed graph with 8 edges and 10 edges. Notice that vertices 5 and 8 have a bidirectional connection.
As you can notice, the graph representation with an adjacency list is way more compact compared to the adjacency matrix. This is due to the fact that there aren’t that many edges in our graph. In some cases, when the number of edges is large enough, it might be more efficient to store the graph in an adjacency matrix.

Challenge: Edges to Adjacency List

Given an undirected graph with v vertices and e edges, you are asked to obtain its adjacency list.

Input

The first line of the input contains two integers v (1 ≤ v ≤ 100 000) and e (1 ≤ e ≤ 100 000).
The following e lines contain pairs of integers v1, v2 (1 ≤ v1, v2 ≤ v) which means that the vertex v1 is connected to the vertex v2 and vice versa.

Output

The program should print the adjacency list of the given graph. Each row should start with the id of a vertex followed by a semicolon (:) and then its connections. The connections on each row should be separated by a space. The order of both the vertices and the connections can be arbitrary.

Examples

Input
Output
8 9 1 4 4 6 3 2 2 1 5 2 5 6 8 5 7 6 7 8
1: 2 4 2: 1 3 5 3: 2 4: 1 6 5: 2 6 8 6: 4 7 5 7: 8 6 8: 5 7

Explanation

An undirected graph with 8 vertices and 9 edges
An undirected graph with 8 vertices and 9 edges

Constraints

Time limit: 2.2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue