Операции на графе
Операции на графе
В задаче необходимо создать неориентированный граф, на котором поддерживаются следующие операции:
- AddEdge(u, v) - добавить в граф ребро между вершинами (u, v);
- Vertex(u) - вывести список вершин, смежных с вершиной u.
Петель и кратных ребер в графе нет.
Входные данные
В первой строке содержится количество вершин в графе n (1 ≤ n ≤ 105
). В следующей строке находится количество операций k (0 ≤ k ≤ 106
). Каждая из следующих строк задает операцию в формате: "1 <число> <число>" или "2 <число>", обозначающие соответственно операции AddEdge(u, v) и Vertex(u).
Гарантируется, что суммарное количество чисел, которое необходимо вывести при выполнении всех операций Vertex, не превосходит 2·105
.
Выходные данные
Для каждой команды Vertex вывести в отдельной строке список смежных вершин указанной вершины. Вершины списка смежности можно выводить в произвольном порядке. Если для указанной вершины смежных нет, то следует вывести пустую строку.
4 4 1 1 2 1 2 3 2 4 2 2
1 3