# Find the Transpose of a Graph

Given a directed graph with `v` vertices and `e` edges, you are asked to find its transpose.
The transpose of a directed graph is a graph obtained by reversing the direction of all its edges. In other words, it's a graph in which all the directed edges of the original graph are reversed.
The transpose of a graph is useful in finding the reverse paths or inverse relationships in the graph. We will see some applications later in the course.

#### 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`.

#### Output

The program should print the adjacency list of the complement 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 4 4 1 2 1 4 2 4 3 4 1: 2: 1 3: 4: 1 2 3
Β

#### Constraints

Time limit: 3.5 seconds

Memory limit: 512 MB

Output limit: 1 MB