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

Два остовных дерева

Два остовных дерева

Лимит времени 2 секунды
Лимит использования памяти 256 MiB

Задан неориентированный граф, рёбра которого можно разбить на два непересекающихся остовных дерева. Вам необходимо найти одно из таких разбиений.

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

Первая строка содержит два натуральных числа n и m - количество вершин и рёбер в графе. Следующие m строк содержат описания рёбер графа. Каждое ребро задаётся номерами концов. Гарантируется, что в графе нет петель, но могут быть кратные рёбра.

Вершины и рёбра графа нумеруются с единицы. Количество вершин не превышает 500, а количество рёбер 1000.

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

Вывести искомое разбиение рёбер графа. В первой строке выведите номера рёбер, которые войдут в первое остовное дерево, во второй - номера рёбер, которые войдут во второе остовное дерево. Каждое ребро графа должно появиться ровно в одной из этих двух строк.

Автор И.Разенштейн, С.Копелиович