Den Graphen vollständig machen
Gegeben ist ein ungerichteter Graph mit
v Knoten (vertices) und e Kanten (edges). Ihre Aufgabe besteht darin, alle Kanten zu ermitteln, die hinzugefügt werden müssen, damit der Graph vollständig wird.Eingabe
Die erste Zeile der Eingabe enthält zwei Ganzzahlen
v (1 ≤ v ≤ 500) und e (1 ≤ e ≤ ).In den folgenden
e Zeilen stehen jeweils zwei ganze Zahlen v1 und v2 (1 ≤ v1, v2 ≤ v), die eine Kante zwischen v1 und v2 darstellen.Ausgabe
Das Programm soll alle Kanten, die zum Vervollständigen des Graphen fehlen, in lexikografischer Reihenfolge ausgeben (nach dem kleineren Knoten aufsteigend). Jede Kante wird in einer eigenen Zeile ausgegeben, wobei die Knoten durch ein Leerzeichen getrennt werden.
Beispiele
Eingabe | Ausgabe |
4 3
1 2
2 3
3 1 | 1 4
2 4
3 4 |
Erklärung
- Der Knoten 4 ist zunächst mit keinem Knoten verbunden, daher muss er mit allen anderen Knoten verbunden werden.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB