Каждая из \(N\) (\(1\le N\le 2\cdot 10^5\)) коров Фермера Джона имеет любимый цвет.
Коровы последовательно помечены \(1\ldots N\), а каждый цвет может быть представлен
целым числом в интервале \(1\ldots N\).
Имеется \(M\) пар коров \((a,b)\) таких, что корова \(b\) восхищается коровой \(a\)
(\(1\le M\le 2\cdot 10^5\)). Возможно, что \(a=b\), в этом случает корова восхищается
сама собой. Для любого цвета \(c\), если коровы \(x\) и \(y\) обе восхищаются коровой с
любимым цветом \(c\), тогда коровы \(x\) и \(y\) разделяют один и тот же любимый цвет.
По данной информации определите назначение коровам любимого цвета так, чтобы
максимизировать количество различных любимых цветов среди всех коров. Поскольку
может существовать несколько таких назначений, выведите лексикографически
наименьшее из них (то есть Вы должны взять назначение, которое минимизирует цвета, назначенные
коровам \(1\ldots N\) в этом порядке).
ФОРМАТ ВВОДА (файл fcolor.in):
Первая строка содержит
\(N\) и
\(M\).
Каждая из последующих \(M\) строк содержит два разделённых пробелом целых числа
\(a\) и \(b\) (\(1\le a,b\le N\)), обозначающих, что корова \(a\) восхищается коровой \(b\).
Каждая пара может появится на вводе более одного раза.
ФОРМАТ ВЫВОДА (файл fcolor.out):
Для каждого \(i\) в интервале \(1\ldots N\), выведите на отдельной строке цвет коровы \(i\)
в желаемом назначении.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9 12
1 2
4 2
5 8
4 6
6 9
2 9
8 7
8 3
7 1
9 4
3 5
3 4
|
1
2
3
1
1
2
3
2
3
|