Нахождение дополнения графа

Дан неориентированный граф с v вершинами и e рёбрами. Требуется найти его дополнение.

Дополнение графа — это граф, в котором проведены рёбра между всеми теми вершинами, которые не соединены в исходном графе. При этом, в дополнении не должно быть рёбер между вершинами, которые имели ребро в исходном графе.

Вход

Первая строка входных данных содержит два целых числа v (1 ≤ v ≤ 500) и e (1 ≤ e ≤ 100 000).

Следующие e строк задают пары целых чисел v1, v2 (1 ≤ v1, v2 ≤ v), где вершина v1 соединена с вершиной v2 (и наоборот).

Выход

Программа должна вывести список смежности для дополнения графа. Каждая строка должна начинаться с идентификатора вершины, за которым следует двоеточие (:), и далее перечисляются её соседи. Соседи в каждой строке разделяются пробелом. Порядок вывода вершин и их соседей не важен.

Примеры