Дано зв’язний неорієнтований граф без петель і кратних ребер. Дозволяється видаляти з нього ребра. Потрібно отримати дерево.
Перший рядок містить два цілі числа (1 \leq n \leq 100) і — кількість вершин і кількість ребер у графі. Далі йдуть пар цілих чисел, кожна з яких задає одне ребро. Гарантовано, що граф зв’язний.
Виведіть n - 1 пар чисел — ребра, що входять у дерево. Ребра можна виводити в будь-якому порядку.

Приклад 1