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

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

Вхідні дані

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

Вершини та ребра графа нумеруються з одиниці. Кількість вершин не перевищує 500, а кількість ребер 1000.

Вихідні дані

Вивести шукане розбиття ребер графа. У першому рядку виведіть номери ребер, які увійдуть у перше остовне дерево, у другому - номери ребер, які увійдуть у друге остовне дерево. Кожне ребро графа повинно появитися рівно у одному з цих двох рядків.