eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Инсайдерская информация

Инсайдерская информация

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Ян работает в рейтинговом агентстве, которое публикует рейтинги лучших университетов. Ирен — журналистка, которая планирует написать скандальную статью о предстоящем рейтинге.

С помощью различных методов социальной инженерии (не будем вдаваться в подробности) Ирэн получила некоторую инсайдерскую информацию от Яна.

В частности, Ирина получила несколько троек (a[i], b[i], c[i]), что означает, что в предстоящем рейтинге университет b[i] стоит между университетами a[i] и c[i]. То есть либо a[i] идет перед b[i], который идет перед c[i], либо наоборот. Все тройки, указанные Яном, непротиворечивы - допустим, реальный рейтинг их всех удовлетворяет.

Чтобы начать работу над первым наброском будущей статьи, Ирен необходимо увидеть хоть какое-то приближение к реальному рейтингу. Она попросила Вас найти предложение рейтинга, в котором удовлетворяется хотя бы половина троек, известных Ирэн.

Вхідні дані

В первой строке записаны целые числа n и m (3n10^5 , 1m10^5), количество включенных в рейтинг университетов и количество троек, которые дал Ирине Ян.

Каждая из следующих m строк содержит три различных целых числа (1a[i], b[i], c[i]n) — университеты, задающие тройку.

Вихідні дані

Выведите предлагаемый рейтинг от первого университета к последнему. Предложенный рейтинг должен удовлетворить не менее m / 2 тройкам. Если таких предложений несколько, выведите любое из них.

Пример

В примере первые две тройки выполняются, а последняя — нет. Следовательно, по крайней мере половина всех троек удовлетворена.

Приклад

Вхідні дані #1
4 3
1 2 3
1 2 3
1 4 3
Вихідні дані #1
4 3 2 1
Джерело 2015 ACM NEERC, Northern Subregion, October 24, Problem I