# 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
,       # Vertex 2
,       # Vertex 3
[],        # Vertex 4
[6, 8],    # Vertex 5
[4, 7],    # Vertex 6
,       # Vertex 7
,       # Vertex 8
]`````` 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