Algorithms and Data Structures

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.
notion image
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: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB

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