Дан граф. Определите для каждой вершины, какой компоненте связности она принадлежит.
Входные данные. Вводится число N (1≤N≤100) - число вершин графа и M - число ребер (0≤M≤10000). Далее записано M пар чисел, задающих ребра графа. Граф неориентированный, в графе могут быть петли и кратные ребра.
Выходные данные. В выходной файл выведите N чисел. i-ое число должно означать номер компоненты связности, которой принадлежит вершина номер i (компоненты связности должны быть пронумерованы натуральными числами от 1 до K, где K - число компонент связности в графе).
| Пример ввода | Пример вывода |
7 5 1 2 1 5 5 2 4 6 7 2 | 2 2 1 3 2 3 2 |