Completar el grafo
Se tiene un grafo no dirigido con
v vértices y e aristas. El objetivo es encontrar todas las aristas que deben añadirse al grafo para que este sea completo.Entrada
La primera línea de la entrada contiene dos números enteros
v (1 ≤ v ≤ 500) y e (1 ≤ e ≤ ).A continuación, se proporcionan
e líneas, cada una con un par de enteros v1, v2 (1 ≤ v1, v2 ≤ v), que representan una arista entre v1 y v2.Salida
El programa debe imprimir todas las aristas que se necesiten agregar al grafo en orden lexicográfico (desde la id de vértice más pequeña hasta la más grande). Cada arista debe imprimirse en una línea independiente, separando los vértices con un espacio.
Ejemplos
Entrada | Salida |
4 3
1 2
2 3
3 1 | 1 4
2 4
3 4 |
Explicación
- El vértice 4 no estaba conectado inicialmente con ninguno de los demás vértices del grafo, por lo que se necesita añadir aristas que lo vinculen con todos los otros vértices.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB