Інсайдерська інформація
Ян працює в рейтинговому агентстві, яке публікує списки найкращих університетів. Ірен — журналістка, яка планує написати сенсаційну статтю про майбутній рейтинг.
Використовуючи різні методи соціальної інженерії (не будемо вдаватися в деталі), Ірен отримала деяку інсайдерську інформацію від Яна.
Зокрема, Ірен дізналася про кілька трійок (a[i], b[i], c[i]), що означає, що в майбутньому рейтингу університет b[i] знаходиться між університетами a[i] і c[i]. Тобто або a[i] йде перед b[i], який йде перед c[i], або навпаки. Усі трійки, надані Яном, не суперечливі — припустимо, що реальний рейтинг їх усіх задовольняє.
Щоб розпочати роботу над першим начерком майбутньої статті, Ірен необхідно побачити хоча б приблизний варіант реального рейтингу. Вона попросила вас знайти варіант рейтингу, в якому буде задоволено хоча б половину трійок, відомих Ірен.
Вхідні дані
У першому рядку записані цілі числа n і m (3 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5), що означають кількість університетів у рейтингу та кількість трійок, які Ян надав Ірен.
Кожен з наступних m рядків містить три різних цілі числа (1 ≤ a[i], b[i], c[i] ≤ n) — університети, що утворюють трійку.
Вихідні дані
Виведіть запропонований рейтинг від першого університету до останнього. Запропонований рейтинг повинен задовольняти не менше m / 2 трійкам. Якщо таких варіантів декілька, виведіть будь-який з них.
Приклад
У прикладі перші дві трійки виконуються, а остання — ні. Отже, принаймні половина всіх трійок задоволена.