Remote Training on Programming

Дан связный неориентированный граф без петель и кратных ребер. Разрешается удалять из него ребра. Требуется получить дерево.

Input

Вначале заданы два числа - N (от 1 до 100) и M - количество вершин и ребер графа соответственно. Далее идет M пар чисел, задающих ребра. Гарантируется, что граф связный.

Output

Выведите N-1 пару чисел - рёбра, которые войдут в дерево. Если есть несколько правильных ответов, выведите любой. Ребра можно выводить в любом порядке.

Sample

4 4
1 2
2 3
3 4
4 1

1 2
2 3
4 3