B. Estradas Faltantes II

Após descobrir quantas estradas ainda faltam para completar a malha viária de Arandu, o governador agora deseja preparar um relatório detalhado contendo todas as ligações ausentes.

Sua tarefa é listar todos os pares de cidades que não possuem estrada direta, sempre no formato a b com a < b.

Constraints

• ( $1 \leq N \leq 1500$ )
• ( $0 \leq M \leq 1500$ )
• ( $1 \leq u_i, v_i \leq N$ )
• As estradas existentes conectam vértices distintos.
• O grafo é simples (sem arestas repetidas).
• Todos os valores da entrada são inteiros.

Input

A entrada é dada no formato:

N M
u1 v1
u2 v2
...
uM vM

Output

Imprima todas as estradas inexistentes no formato:

a b

com a < b. A ordem das linhas é livre.

Exemplo

Entrada 1

4 2
1 2
3 4

Saída 1

1 3
1 4
2 3
2 4

Entrada 2

5 2
1 5
2 3

Saída 2

1 2
1 3
1 4
2 4
2 5
3 4
3 5
4 5