Улюблені кольори
У кожної корови фермера Джона є улюблений колір. Корови пронумеровані від 1 до n, і кожен колір може бути представлений цілим числом у діапазоні від 1 до n.
Існують m пар корів (a, b), де корова b захоплюється коровою a (1 ≤ m ≤ 2 * 10^5). Можливо, що a = b, і в такому випадку корова милується собою. Для будь-якого кольору c, якщо корови x і y захоплюються коровою улюбленого кольору c, тоді x і y повинні мати однаковий улюблений колір.
Вам потрібно визначити розподіл улюблених кольорів серед корів так, щоб кількість різних улюблених кольорів була максимальною. Якщо існує кілька можливих розподілів, виберіть лексикографічно найменший (тобто розподіл, який мінімізує кольори, призначені коровам 1 .. n у цьому порядку).
Вхідні дані
Перша строка містить n (1 ≤ n ≤ 2 * 10^5) і m. Кожна з наступних m строк містить два цілі числа a і b (1 ≤ a, b ≤ n), що означає, що корова b захоплюється коровою a. Одна і та ж пара може з'являтися у вхідних даних більше одного разу.
Вихідні дані
Для кожного i від 1 до n, виведіть колір корови i у бажаному розподілі з нового рядка.
Приклад
На рисунку нижче кружки з напівжирними межами представляють корів улюбленого кольору 1.
