Інсайдерська інформація#7620

Інсайдерська інформація

1 секунда

128 мегабайтів

Дуже складна

Ян працює в рейтинговому агентстві, яке публікує списки найкращих університетів. Ірен — журналістка, яка планує написати сенсаційну статтю про майбутній рейтинг.

Використовуючи різні методи соціальної інженерії (не будемо вдаватися в деталі), Ірен отримала деяку інсайдерську інформацію від Яна.

Зокрема, Ірен дізналася про кілька трійок ( $a_{i}$ a_i, $b_{i}$ b_i, $c_{i}$ c_i), що означає, що в майбутньому рейтингу університет $b_{i}$ b_i знаходиться між університетами $a_{i}$ a_i і $c_{i}$ c_i. Тобто або $a_{i}$ a_i йде перед $b_{i}$ b_i, який йде перед $c_{i}$ c_i, або навпаки. Усі трійки, надані Яном, не суперечливі — припустимо, що реальний рейтинг їх усіх задовольняє.

Щоб розпочати роботу над першим начерком майбутньої статті, Ірен необхідно побачити хоча б приблизний варіант реального рейтингу. Вона попросила вас знайти варіант рейтингу, в якому буде задоволено хоча б половину трійок, відомих Ірен.

Вхідні дані

У першому рядку записані цілі числа $n$ і $m$ ( $3 \leq n \leq 1 0^{5}$ 3 \le n \le 10^5, $1 \leq m \leq 1 0^{5}$ 1 \le m \le 10^5), що означають кількість університетів у рейтингу та кількість трійок, які Ян надав Ірен.

Кожен з наступних $m$ рядків містить три різних цілі числа ( $1 \leq a_{i}, b_{i}, c_{i} \leq n$ 1 \le a_i, b_i, c_i \le n) — університети, що утворюють трійку.

Вихідні дані

Виведіть запропонований рейтинг від першого університету до останнього. Запропонований рейтинг повинен задовольняти не менше $m /2$ трійкам. Якщо таких варіантів декілька, виведіть будь-який з них.

Приклади

У прикладі перші дві трійки виконуються, а остання — ні. Отже, принаймні половина всіх трійок задоволена.

Приклад 1