Сделать граф полным
Допустим, у нас есть неориентированный граф с
v вершинами и e рёбрами. Требуется найти все рёбра, которые нужно добавить, чтобы этот граф стал полным.Входные данные
Первая строка входных данных содержит два целых числа:
v (1 ≤ v ≤ 500) и e (1 ≤ e ≤ ).В следующих
e строках содержатся пары целых чисел v1, v2 (1 ≤ v1, v2 ≤ v), обозначающие ребро между v1 и v2.Выходные данные
Необходимо вывести все рёбра, которые следует добавить в граф, причём в лексикографическом порядке (от меньшего номера вершины к большему). Каждый требуемый к добавлению ребро следует выводить в отдельной строке, при этом вершины должны быть разделены пробелом.
Примеры
Входные данные | Выходные данные |
4 3
1 2
2 3
3 1 | 1 4
2 4
3 4 |
Объяснение
- Вершина 4 изначально не была связана ни с одной из других вершин, поэтому необходимо добавить рёбра, соединяющие её со всеми остальными вершинами.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB