Le nain Entrepreneur souhaite lancer une entreprise de visites guidées à Wroclaw. Ses visites s'effectueront en bus à travers la ville, et chaque fois que le bus passera devant un monument intéressant, une description enregistrée de ce monument sera diffusée par le système sonore du bus.

Le nain a préparé une carte qui comprend $N$ monuments, numérotés de $1$ à $N$, et $M$ rues bidirectionnelles, chacune reliant une paire de monuments. Une caractéristique surprenante de sa carte est que chaque monument est incident à au plus $7$ rues. Chaque visite sera une séquence de $3$ monuments différents, où deux monuments consécutifs quelconques sont reliés par une rue.

Maintenant, avant de choisir les visites, le nain doit préparer les descriptions enregistrées des monuments et embaucher des narrateurs professionnels. Il n'a les moyens d'embaucher que $4$ narrateurs, et il ne peut enregistrer la description de chaque monument qu'une seule fois, en faisant appel à un unique narrateur. Cependant, l'Entrepreneur craint que même la voix du meilleur narrateur ne devienne monotone pour le public ; il a donc décidé que dans toute visite possible, les $3$ descriptions ne peuvent pas toutes être lues par le même narrateur.

Le nain n'a pas encore arrêté son choix sur une visite précise, et sa réservation au studio d'enregistrement est pour demain. Aidez-le à attribuer les narrateurs aux monuments de sorte qu'ils ne soient jamais tous commentés par le même narrateur dans aucune visite possible.

Entrée

La première ligne d'entrée contient deux entiers séparés par un espace, $N$ et $M$, désignant le nombre de monuments et le nombre de rues sur la carte du nain.

Les $M$ lignes suivantes décrivent les rues reliant les monuments, où la $i$-ème ligne contient deux entiers séparés par un espace, $a_i$ et $b_i$, désignant les numéros des monuments reliés par cette rue.

Sortie

Affichez une seule ligne de $N$ entiers séparés par des espaces, $c_1, \dots, c_N$, où $c_i$ ($1 \le c_i \le 4$) désigne l'identifiant du narrateur qui doit enregistrer la description du $i$-ème monument.

S'il existe plusieurs solutions, affichez n'importe laquelle d'entre elles. Vous pouvez supposer que dans chaque cas de test, il existe au moins une solution.

Contraintes

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

aucune rue ne relie un monument à lui-même,

aucune paire de monuments n'est reliée par plus d'une rue,

chaque monument est incident à au plus $7$ rues.

Exemples

Entrée 1

3 3
1 2
2 3
3 1

Sortie 1

2 1 1

Entrée 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

Sortie 2

2 3 1 3 1 3 1 1