Find the Complement of a Graph
Given an undirected graph with
v vertices and e edges, you are asked to find its complement. The complement of a graph is a graph that has edges between all the nodes that don’t have an edge in the original one, while at the same time, not having an edge between vertices where an edge is present in the original graph.
.png?table=block&id=6a2a8d26-9da6-4fea-a427-d82f38c10350&cache=v2)
Input
The first line of the input contains two integers
v (1 ≤ v ≤ 500) 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 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
4 2
4 1
3 4 | 1: 3
2: 3
3: 1 2
4: |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB