#312 강한 연결 요소 검증

Statement

Statement language

정점이 $1$ 번부터 $N$ 번까지 번호가 붙은 방향 그래프가 주어진다. 각 정점이 속한 강한 연결 요소의 번호를 출력하여라.

강한 연결 요소 번호는 다음과 같이 정한다. 각 강한 연결 요소의 대표값을 그 요소에 속한 가장 작은 정점 번호로 정의한다. 대표값이 작은 강한 연결 요소부터 $1,2,\cdots$ 번을 붙인다.

입력은 다음과 같은 형식으로 주어진다.

$N\ M$ $u_1\ v_1$ $u_{2}$

첫째 줄에 $N$ 개의 정수를 출력한다. $i$ 번째 정수는 $i$ 번 정점이 속한 강한 연결 요소 번호이다.

#	Score	Constraints
1	20	$N \leq 200$ , $M \leq 500$
2	80	추가적인 제약조건이 없다.

Input

Output

1 1 1 2 2 3 4