Description

Given a undirected graph G with N vertices and M edges. The vertices are numbered from 1 to N.

Please find the complement G' of the graph G. The complement of a graph G is a graph G' such that there is an edge between two vertices in G' if and only if there is no edge between the two vertices in G.

Input

The first line contains two integers N and M (1 ≤ N ≤ 1000, 0 ≤ M ≤ N*(N-1)/2) - the number of vertices and edges in the graph G.

Each of the next M lines contains two integers u and v (1 ≤ u, v ≤ N, u ≠ v) - the vertices connected by an edge.

It's not guaranteed that G have no multiple edges.

Output

Print the edges of the complement graph G' in the following format:

u1 v1
u2 v2
u3 v3
...

where (u1, v1), (u2, v2), (u3, v3), ... are the edges of the complement graph G'.

Please make sure that:

1. u_i < v_i
2. u_i < u_j if i < j.

Sample Input  Download

Sample Output  Download

Tags

Discuss