페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4169

Favorite Colors 1초 512MB

문제

Each of Farmer John's N cows (1\le N\le 2\cdot 10^5) has a favorite color. The cows are conveniently labeled 1\ldots N (as always), and each color can be represented by an integer in the range 1\ldots N.

There exist M pairs of cows (a,b) such that cow b admires cow a (1\le M\le 2\cdot 10^5). It is possible that a=b, in which case a cow admires herself. For any color c, if cows x and y both admire a cow with favorite color c, then x and y share the same favorite color.

Given this information, determine an assignment of cows to favorite colors such that the number of distinct favorite colors among all cows is maximized. As there are multiple assignments that satisfy this property, output the lexicographically smallest one (meaning that you should take the assignment that minimizes the colors assigned to cows 1\ldots N in that order).

SCORING:

  • Test cases 2-3 satisfy N,M\le 10^3.

  • Test cases 4-10 satisfy no additional constraints.

Problem credits: William Lin and Benjamin Qi


입력

The first line contains N and M.

The next M lines each contain two space-separated integers a and b (1\le a,b\le N), denoting that cow b admires cow a. The same pair may appear more than once in the input.


출력

For each i in 1\ldots N, output the color of cow i in the desired assignment on a new line.


예제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

In the image below, the circles with bolded borders represent the cows with favorite color 1.


출처

USACO 2020 US Open Gold

역링크 공식 문제집만