Il nano Imprenditore vuole avviare un'attività di visite guidate a Breslavia. I suoi tour si svolgeranno in autobus attraversando la città e, ogni volta che l'autobus passerà davanti a un monumento interessante, una descrizione registrata di quel monumento verrà riprodotta dall'impianto audio dell'autobus.

Il nano ha preparato una mappa che include $N$ monumenti, numerati da $1$ a $N$, e $M$ strade a doppio senso, ciascuna delle quali collega una coppia di monumenti. Una caratteristica sorprendente della sua mappa è che ogni monumento è incidente ad al massimo $7$ strade. Ogni tour sarà una sequenza di $3$ monumenti diversi, in cui ogni coppia di monumenti consecutivi è collegata da una strada.

Ora, prima di scegliere i tour, il nano deve preparare le descrizioni registrate dei monumenti e assumere dei narratori professionisti. Può permettersi di assumere solo $4$ narratori e può registrare la descrizione di ciascun monumento una sola volta, utilizzando un singolo narratore. Tuttavia, l'Imprenditore teme che persino la voce del miglior narratore possa diventare monotona per il pubblico, quindi ha deciso che in nessun tour possibile tutte e $3$ le descrizioni possano essere narrate dallo stesso narratore.

Il nano non ha ancora deciso alcun tour specifico e la sua prenotazione dello studio di registrazione è per domani. Aiutalo ad assegnare i narratori ai monumenti in modo che non vengano narrati tutti dallo stesso narratore in nessun tour possibile.

Input

La prima riga di input contiene due interi separati da spazio $N$ e $M$, che indicano il numero di monumenti e il numero di strade sulla mappa del nano.

Le successive $M$ righe descrivono le strade che collegano i monumenti, dove la $i$-esima riga contiene due interi separati da spazio $a_i$ e $b_i$ che indicano i numeri dei monumenti collegati da questa strada.

Output

Stampa una singola riga di $N$ interi separati da spazio $c_1, \dots, c_N$, dove $c_i$ ($1 \le c_i \le 4$) indica l'identificativo del narratore che dovrebbe registrare la descrizione dell'$i$-esimo monumento.

Se esistono molte soluzioni, stampane una qualsiasi. Puoi supporre che in ogni caso di test esista almeno una soluzione.

Vincoli

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

nessuna strada collega alcun monumento a se stesso,

nessuna coppia di monumenti è collegata da più di una strada,

ogni monumento è incidente ad al massimo $7$ strade.

Esempi

Input 1

3 3
1 2
2 3
3 1

Output 1

2 1 1

Input 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

Output 2

2 3 1 3 1 3 1 1