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, не перевищує 2 * 10^5.

Вихідні дані

Для кожної команди Vertex вивести в окремому рядку вивести список суміжних вершин вказаної вершини. Вершини списку суміжності можна виводити у довільному порядку. Якщо для вказаної вершини суміжних немає, то слід вивести порожній рядок.

prb2472.gif

Приклад

Вхідні дані #1
4
4
1 1 2
1 2 3
2 4
2 2
Вихідні дані #1
1 3