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

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

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

Вхідні дані

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

Вихідні дані

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

Приклад

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