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