좋아하는 색

농부 존의 소는 $N$마리($1\le N\le 2\cdot 10^5$)이며, 각 소에게는 좋아하는 색이 있다. 소는 $1\ldots N$으로 번호가 매겨져 있고, 색은 $1\ldots N$ 범위의 정수로 나타낸다.

소 쌍 $(a,b)$가 $M$개 ($1\le M\le 2\cdot 10^5$) 있으며, 소 $b$가 소 $a$를 존경한다. $a=b$인 쌍도 있을 수 있으며, 이때 소는 자기 자신을 존경한다. 임의의 색 $c$에 대해, 소 $x$와 $y$가 모두 좋아하는 색이 $c$인 소를 존경하면, $x$와 $y$는 같은 색을 좋아한다.

좋아하는 색의 서로 다른 개수가 최대가 되도록 각 소에 좋아하는 색을 배정하라. 이를 만족하는 배정이 여러 개라면, 사전순으로 가장 작은 배정을 출력한다. 즉, 1번 소부터 $N$번 소까지 순서대로 색을 비교했을 때 가장 작은 배정이다.

첫 줄에 $N$과 $M$이 주어진다. 이어지는 $M$개의 줄에는 공백으로 구분된 두 정수 $a$와 $b$ ($1\le a,b\le N$)가 주어지며, 이는 소 $b$가 소 $a$를 존경한다는 뜻이다. 같은 쌍이 입력에 두 번 이상 나올 수 있다.

$i=1\ldots N$마다, 원하는 배정에서 소 $i$의 색을 한 줄에 하나씩 출력한다.

아래 그림에서 테두리가 굵은 원이 좋아하는 색이 1인 소이다.