e-olymp
Змагання

ADA Classes - Depth First Search

Отримай дерево

Задано зв'язний неорієнтовний граф без петель і кратних ребер. Дозволяється видаляти з нього ребра. Потрібно отримати дерево.

Вхідні дані

Перший рядок містить кількість вершин n (1n100) та кількість ребер m графу відповідно. Наступні m пар чисел задають ребра графу. Гарантується, що граф зв'язний.

Вихідні дані

Виведіть n - 1 пару чисел - ребра, які увійдуть у дерево. Ребра можна виводити у довільному порядку.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
4 4
1 2
2 3
3 4
4 1
Вихідні дані #1
1 2
2 3
3 4