Поиск транспонированного графа

Дан ориентированный граф с v вершинами и e рёбрами; ваша задача — найти его транспонирование.

Транспонирование ориентированного графа — это граф, в котором направление всех рёбер исходного графа обращено в противоположную сторону. Другими словами, если в исходном графе есть дуга из v1 в v2, то в транспонированном графе будет дуга из v2 в v1.

Транспонированный граф полезен для поиска обратных путей или инверсных отношений в исходном графе. Позже в курсе мы рассмотрим некоторые его применения.

Входные данные

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

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

Выходные данные

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

Примеры