eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Операции на графе

Операции на графе

Лимит времени 3 секунды
Лимит использования памяти 128 MiB

В задаче необходимо создать неориентированный граф, на котором поддерживаются следующие операции:

  1. AddEdge(u, v) - добавить в граф ребро между вершинами (u, v);

  2. Vertex(u) - вывести список вершин, смежных с вершиной u.

Петель и кратных ребер в графе нет.

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

В первой строке содержится количество вершин в графе n (1n10^5). В следующей строке находится количество операций k (0k10^6). Каждая из следующих строк задает операцию в формате: "1 <число> <число>" или "2 <число>", обозначающие соответственно операции AddEdge(u, v) и Vertex(u).

Гарантируется, что суммарное количество чисел, которое необходимо вывести при выполнении всех операций Vertex, не превосходит 10^5.

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

Для каждой команды Vertex вывести в отдельной строке список смежных вершин указанной вершины. Вершины списка смежности можно выводить в произвольном порядке. Если для указанной вершины смежных нет, то следует вывести пустую строку.

prb2472.gif

Пример

Входные данные #1
4
4
1 1 2
1 2 3
2 4
2 2
Выходные данные #1
1 3