Kurcaci Sang Pengusaha ingin memulai bisnis pemandu wisata di Wroclaw. Tur-turnya akan dilakukan dengan bus yang melintasi kota, dan setiap kali bus melewati sebuah markah tanah (landmark) yang menarik, rekaman deskripsi dari markah tanah tersebut akan diputar melalui sistem tata suara bus.

Sang kurcaci telah menyiapkan sebuah peta yang mencakup $N$ markah tanah, yang diberi nomor dari $1$ hingga $N$, serta $M$ jalan dua arah, yang masing-masing menghubungkan sepasang markah tanah. Fitur mengejutkan dari petanya adalah bahwa setiap markah tanah bersisian dengan paling banyak $7$ jalan. Setiap tur akan berupa barisan $3$ markah tanah berbeda, di mana setiap dua markah tanah yang berurutan dihubungkan oleh sebuah jalan.

Sekarang, sebelum memilih tur, sang kurcaci perlu menyiapkan rekaman deskripsi dari markah-markah tanah tersebut dan menyewa narator profesional. Ia hanya mampu menyewa $4$ narator, dan ia hanya dapat merekam deskripsi untuk setiap markah tanah satu kali saja, menggunakan satu narator. Namun, Sang Pengusaha khawatir bahwa suara narator terbaik sekalipun dapat terasa monoton bagi para pendengar, sehingga ia memutuskan bahwa dalam tur mana pun yang mungkin, ketiga ($3$) deskripsi tidak bolehsemuanya dinarasikan oleh narator yang sama.

Sang kurcaci belum memutuskan tur spesifik mana yang akan dipilih, sedangkan reservasi studio rekamannya adalah besok. Bantulah ia menugaskan narator ke setiap markah tanah sehingga ketiganya tidak akan dinarasikan oleh narator yang sama dalam tur mana pun yang mungkin.

Masukan

Baris pertama masukan berisi dua bilangan bulat yang dipisahkan spasi, $N$ dan $M$, yang menyatakan banyaknya markah tanah dan banyaknya jalan pada peta sang kurcaci.

$M$ baris berikutnya mendeskripsikan jalan-jalan yang menghubungkan markah tanah, di mana baris ke-$i$ berisi dua bilangan bulat yang dipisahkan spasi, $a_i$ dan $b_i$, yang menyatakan nomor-nomor markah tanah yang dihubungkan oleh jalan tersebut.

Keluaran

Cetak satu baris berisi $N$ bilangan bulat yang dipisahkan spasi, $c_1, \dots, c_N$, di mana $c_i$ ($1 \le c_i \le 4$) menyatakan nomor identitas narator yang harus merekam deskripsi untuk markah tanah ke-$i$.

Jika terdapat banyak solusi, cetak yang mana saja. Anda dapat mengasumsikan bahwa pada setiap kasus uji pasti terdapat setidaknya satu solusi.

Batasan

$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$

tidak ada jalan yang menghubungkan suatu markah tanah ke dirinya sendiri,

tidak ada pasangan markah tanah yang dihubungkan oleh lebih dari satu jalan,

setiap markah tanah bersisian dengan paling banyak $7$ jalan.

Contoh

Masukan 1

3 3
1 2
2 3
3 1

Keluaran 1

2 1 1

Masukan 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

Keluaran 2

2 3 1 3 1 3 1 1