Tornando o Grafo Completo
Dado um grafo não direcionado com
v vértices e e arestas, o objetivo é encontrar todas as arestas que precisam ser adicionadas ao grafo para torná-lo completo.Entrada
A primeira linha da entrada contém dois inteiros
v (1 ≤ v ≤ 500) e e (1 ≤ e ≤ ).As próximas
e linhas contêm pares de inteiros v1, v2 (1 ≤ v1, v2 ≤ v), representando uma aresta entre v1 e v2.Saída
O programa deve imprimir todas as arestas que precisam ser adicionadas ao grafo em ordem lexicográfica (considerando primeiro o vértice de menor identificação). Cada aresta deve ser impressa em uma linha separada, com os vértices separados por um espaço.
Exemplos
Entrada | Saída |
4 3
1 2
2 3
3 1 | 1 4
2 4
3 4 |
Explicação
- O vértice 4 não estava inicialmente conectado a nenhum dos demais vértices do grafo. Portanto, precisamos conectá-lo a todos os outros vértices.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB