Make the Graph Complete

Given an undirected graph with v vertices and e edges, you are asked to find all the edges that need to be added to the graph to make it complete.

Input

The first line of the input contains two integers v (1 ≀ v ≀ 500) and e (1 ≀ e ≀ ).
The following e lines contain pairs of integers v1, v2 (1 ≀ v1, v2 ≀ v) representing an edge between v1 and v2.

Output

The program should print all the edges that need to be added to the graph in lexicographical order (from the smallest vertex id to the largest). All the edges need to be printed on separate lines, while the vertices should be separated by a space.

Examples

Input
Output
4 3 1 2 2 3 3 1
1 4 2 4 3 4

Explanation

  1. Vertex 4 was not initially connected to any of the vertices in the graph. So, we should connect it to all the other vertices.

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

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