Background

2102년 지구는 멸망한다. 이는 국제적 항공 시스템이 복잡한 탓에 바이너리(=호남선)의 무자비한 확산을 막지 못했기 때문이다.
멸망하는 지구를 지키기 위해서 사파리월드의 긴급 의회가 소집되었고, 사파리 월드 의원들은 의외로 결단이 빨라서 다음과 같은 결론에 이른다.

'한 국가에서 출발하는 항공편의 목적지는 모두 같은 국가에 포함되어야 한다'

이는 항공편 x->a, y->b가 존재할 때 x와 y가 같은 국가에 포함된다면 a와 b는 같은 국가에 포함되어야 한다는 것이다.

이러한 조건을 만족하도록 공항들을 K개의 국가에 다시 배정할 때, 사파리 월드 의원들은 K가 최대화되어 최대한 많은 국가가 공항을 나눠 가지기를 원한다.

N개의 공항과 M개의 항공편이 존재할 때 조건을 만족하며 최대한 많은 국가에 공항을 배정할 수 있도록 각 공항이 속하는 국가를 결정하시오.
만약 그런 방법이 여러 가지가 존재한다면 그중 사전 순으로 가장 앞서는 것을 출력하시오.
각 국가는 1에서 N 사이의 숫자로 표현된다.
항공편 a->a가 존재할 수 있다.

Input

첫 줄에는 공항의 수 N과 항공편의 수 M이 주어진다
둘째 줄부터 M+1까지 각각 2개의 자연수 a, b (1<=a,b<=N)이 주어진다. 이는 a공항에서 b공항으로의 항공편이 존재함을 의미한다.
동일한 쌍이 입력에 두 번 이상 나타날 수 있다.

[입력값의 정의역]

Subtask 1: N<=10, M<=25
Subtask 2: N, M<=200000

Output

각각의 공항이 속하는 국가의 숫자를 한 줄에 하나씩 출력한다.

(사진 1)

예제의 연결 관계를 그래프로 나타내면 위와 같다.
이때 
1, 4, 5번 공항이 1번 국가에 속하고
2, 6, 8번 공항이 2번 국가에 속하고
3, 7, 9번 공항이 3번 국가에 속하면

1번 국가에 속하는 공항에서 출발하는 항공편의 도착지는 모두 2번 국가에 속하고
2번 국가에 속하는 공항에서 출발하는 항공편의 도착지는 모두 3번 국가에 속하고
3번 국가에 속하는 공항에서 출발하는 항공편의 도착지는 모두 1번 국가에 속하므로 조건을 만족한다

이 때의 답은
1
2
3
1
1
2
3
2
3
이고 3국가 이상으로 배정하는 방법은 없으며 이보다 사전순으로 앞서는 경우는 없다.

IO Example

입력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
1
2
3
1
1
2
3
2
3