El enano Empresario quiere poner en marcha un negocio de guías turísticos en Breslavia. Sus recorridos se realizarán en autobús conduciendo por la ciudad y, cada vez que el autobús pase junto a un monumento interesante, se reproducirá una descripción grabada de dicho monumento a través del sistema de sonido del autobús.

El enano ha preparado un mapa que incluye $N$ monumentos, numerados del $1$ al $N$, y $M$ calles bidireccionales, cada una de las cuales conecta un par de monumentos. Una característica sorprendente de su mapa es que cada monumento es incidente a como máximo $7$ calles. Cada recorrido será una secuencia de $3$ monumentos diferentes, donde cada par de monumentos consecutivos está conectado por una calle.

Ahora, antes de elegir los recorridos, el enano necesita preparar las descripciones grabadas de los monumentos y contratar a narradores profesionales. Solo puede permitirse contratar a $4$ narradores, y puede grabar la descripción de cada monumento una sola vez, utilizando un único narrador. Sin embargo, al Empresario le preocupa que incluso la voz del mejor narrador pueda volverse monótona para el público, por lo que ha decidido que, en cualquier recorrido posible, las $3$ descripciones no pueden ser narradas todas por el mismo narrador.

El enano aún no se ha decidido por ningún recorrido específico y su reserva en el estudio de grabación es mañana. Ayúdale a asignar narradores a los monumentos para que no sean narrados por el mismo narrador en ningún recorrido posible.

Entrada

La primera línea de entrada contiene dos enteros separados por un espacio, $N$ y $M$, que denotan el número de monumentos y el número de calles en el mapa del enano.

Las siguientes $M$ líneas describen las calles que conectan los monumentos, donde la $i$-ésima línea contiene dos enteros separados por un espacio, $a_i$ y $b_i$, que denotan los números de los monumentos conectados por esa calle.

Salida

Imprime una sola línea con $N$ enteros separados por espacios, $c_1, \dots, c_N$, donde $c_i$ ($1 \le c_i \le 4$) denota el identificador del narrador que debe grabar la descripción del $i$-ésimo monumento.

Si hay muchas soluciones, imprime cualquiera de ellas. Puedes suponer que en cada caso de prueba existe alguna solución.

Restricciones

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

ninguna calle conecta un monumento consigo mismo,

ningún par de monumentos está conectado por más de una calle,

cada monumento es incidente a como máximo $7$ calles.

Ejemplos

Entrada 1

3 3
1 2
2 3
3 1

Salida 1

2 1 1

Entrada 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

Salida 2

2 3 1 3 1 3 1 1