사업가 드워프는 브로츠와프에서 관광 가이드 사업을 시작하려고 합니다. 그의 투어는 시내를 달리는 버스로 진행되며, 버스가 흥미로운 명소를 지나갈 때마다 버스 음향 시스템을 통해 해당 명소에 대한 녹음된 설명이 재생됩니다.

드워프는 $1$부터 $N$까지 번호가 매겨진 $N$개의 명소와 각각 한 쌍의 명소를 연결하는 $M$개의 양방향 거리로 이루어진 지도를 준비했습니다. 그의 지도가 가진 놀라운 특징은 모든 명소에 연결된 거리가 최대 $7$개라는 점입니다. 모든 투어는 서로 다른 $3$개의 명소로 이루어진 수열이며, 연속한 두 명소는 항상 거리로 연결되어 있습니다.

이제 투어를 선정하기 전에, 드워프는 명소에 대한 녹음된 설명을 준비하고 전문 성우들을 고용해야 합니다. 그는 성우를 $4$명까지만 고용할 여력이 있으며, 모든 명소의 설명은 단 한 명의 성우를 사용하여 한 번만 녹음할 수 있습니다. 하지만 사업가는 아무리 뛰어난 성우의 목소리라도 청중에게 단조롭게 느껴질 수 있다고 걱정하여, 가능한 어떤 투어에서도 $3$개의 설명이 모두 같은 성우에 의해 낭독되지 않도록 하기로 결정했습니다.

드워프는 아직 구체적인 투어 코스를 정하지 못했는데, 녹음실 예약은 바로 내일입니다. 가능한 어떤 투어에서도 모두 같은 성우가 낭독하는 일이 없도록 각 명소에 성우를 배정하는 것을 도와주세요.

입력

입력의 첫째 줄에는 드워프의 지도에 있는 명소의 개수와 거리의 개수를 나타내는 공백으로 구분된 두 정수 $N$과 $M$이 주어집니다.

다음 $M$개의 줄에는 명소들을 연결하는 거리가 설명되며, 그중 $i$번째 줄에는 해당 거리로 연결된 두 명소의 번호를 나타내는 공백으로 구분된 두 정수 $a_i$와 $b_i$가 주어집니다.

출력

공백으로 구분된 $N$개의 정수 $c_1, \dots, c_N$을 한 줄에 출력합니다. 여기서 $c_i$ ($1 \le c_i \le 4$)는 $i$번째 명소의 설명을 녹음해야 하는 성우의 번호를 나타냅니다.

해가 여러 개인 경우 아무것이나 출력해도 됩니다. 모든 테스트 케이스에서 해가 항상 존재한다고 가정해도 좋습니다.

제한

$1 \le N \le 10^6$

$1 \le M \le 3.5 \cdot 10^6$

$1 \le a_i, b_i \le N$

$a_i \neq b_i$

어떤 거리도 명소를 자기 자신과 연결하지 않습니다.

어떤 한 쌍의 명소도 두 개 이상의 거리로 연결되어 있지 않습니다.

각 명소는 최대 $7$개의 거리에 인접해 있습니다.

예제

입력 1

3 3
1 2
2 3
3 1

출력 1

2 1 1

입력 2

8 13
1 2
1 3
1 4
1 5
1 6
1 7
2 3
3 4
4 5
5 6
6 7
7 8
8 2

출력 2

2 3 1 3 1 3 1 1