Инсайдерская информация
Ян работает в рейтинговом агентстве, которое публикует рейтинги лучших университетов. Ирен — журналистка, которая планирует написать скандальную статью о предстоящем рейтинге.
С помощью различных методов социальной инженерии (не будем вдаваться в подробности) Ирэн получила некоторую инсайдерскую информацию от Яна.
В частности, Ирина получила несколько троек (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 тройкам. Если таких предложений несколько, выведите любое из них.
Пример
В примере первые две тройки выполняются, а последняя — нет. Следовательно, по крайней мере половина всех троек удовлетворена.