У каждой коровы фермера Джона есть любимый цвет. Коровы пронумерованы числами от 1 до n (как всегда), и каждый цвет может быть представлен целым числом в диапазоне от 1 до n.

Существуют m пар коров (a, b) таких что корова b восхищается коровой a (1 ≤ m ≤ 2 * 105). Возможно, что a = b, и в этом случае корова любуется собой. Для любого цвета c, если коровы x и y восхищаются коровой любимого цвета c, тогда x и y имеют одинаковый любимый цвет.

По этой информации определите присвоение коровам любимых цветов так, чтобы количество различных любимых цветов среди всех коров было максимальным. Поскольку существует несколько назначений, которые удовлетворяют этому свойству, выведите лексикографически наименьшее из них (это означает, что Вы должны взять назначение, которое минимизирует цвета, назначенные коровам 1 .. n в этом порядке).

Входные данные

Первая строка содержит n (1 ≤ n ≤ 2 * 105) и m. Каждая из следующих m строк содержит два целых числа a и b (1 ≤ a, b ≤ n), обозначая, что корова b восхищается коровой a. Одна и та же пара может появляться во входных данных более одного раза.

Выходные данные

Для каждого i из 1..n, выведите цвет коровы i в желаемом назначении с новой строки.

Пример

На рисунке ниже кружки с полужирными границами представляют коров любимого цвета 1.