Задачі
Два остовних дерева
Два остовних дерева
Задано неорієнтовний граф, ребра якого можна розбити на два остовних дерева, що не перетинаються. Вам необхідно знайти одне з таких розбиттів.
\InputFile
Перший рядок містить два натуральних числа \textbf{n }та \textbf{m }- кількість вершин та ребер у графі. Наступні \textbf{m }рядків містять описи ребер графа. Кожне ребро задається номерами кінців. Гарантується, що у графі немає петель, але можуть бути кратні ребра.
Вершини та ребра графа нумеруються з одиниці. Кількість вершин не перевищує \textbf{500}, а кількість ребер \textbf{1000}.
\OutputFile
Вивести шукане розбиття ребер графа. У першому рядку виведіть номери ребер, які увійдуть у перше остовне дерево, у другому - номери ребер, які увійдуть у друге остовне дерево. Кожне ребро графа повинно появитися рівно у одному з цих двох рядків.