Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Получи дерево

(Время: 1 сек. Память: 16 Мб Сложность: 51%)

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

Входные данные

Входной файл INPUT.TXT содержит два целых числа: N и M – количество вершин и ребер графа соответственно (1 ≤ N ≤ 100, 0 ≤ M ≤ N∙(N-1)/2). Далее идет M пар чисел, задающих ребра.

Выходные данные

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

Пример

INPUT.TXTOUTPUT.TXT
14 4
1 2
2 3
3 4
4 1
1 2
2 3
3 4

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Алгоритм Флойда
 Алгоритм Форда-Беллмана
 Алгоритм Дейкстры
 Минимальный каркас
 Эйлеров цикл, конденсация
 Паросочетания
 A. Получи дерево
 B. Минимальный каркас
 C. Связанное множество
 D. Остовное дерево
 E. Школы
 F. Печатная схема

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru