Олимпиады по программированию

olympiads.ru

Дистанционные семинары
Оглавление
Как пользоваться
Система проверки задач
Регистрация, изменение настроек
Страница сдачи решений
Результаты
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике

Дистанционные семинары
по подготовке к олимпиадам по информатике

Задача 09-2. Получи дерево

Имя входного файла input.txt
Имя выходного файла output.txt
Максимальное время работы на одном тесте: 5 секунд

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

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

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

Пример

input.txt output.txt
4 4
1 2
2 3
3 4
4 1
1 2
2 3
3 4