起業家ドワーフは、ヴロツワフで観光ガイド事業を始めたいと考えています。彼のツアーは市内を走るバスで行われ、バスが興味深い名所を通過するたびに、バス内の音響システムからその名所の録音された解説が流れます。

ドワーフは、$1$ から $N$ までの番号が付けられた $N$ 個の名所と、それぞれ一対の名所を結ぶ $M$ 本の双方向の通りを含む地図を用意しました。彼の地図の驚くべき特徴は、どの名所も高々 $7$ 本の通りにしか接続していないことです。すべてのツアーは $3$ つの異なる名所の列であり、連続する 2 つの名所はすべて通りで結ばれています。

さて、ツアーを選ぶ前に、ドワーフは名所の録音解説を準備し、プロのナレーターを雇う必要があります。彼には $4$ 人のナレーターを雇う余裕しかなく、各名所の解説は 1 人のナレーターを使って 1 回だけ録音することができます。しかし、起業家はどんなに優れたナレーターの声であっても聴衆にとっては単調に感じられるかもしれないと懸念しており、考えられるどのツアーにおいても、$3$ つの解説すべてが同じナレーターによって語られることがないように決めました。

ドワーフはまだ具体的なツアーを決めていませんが、録音スタジオの予約は明日です。考えられるどのツアーにおいても同じナレーターだけで語られることがないように、各名所にナレーターを割り当てるのを手伝ってください。

入力

入力の 1 行目には、ドワーフの地図上の名所の数と通りの数を表す、空白で区切られた 2 つの整数 $N$ と $M$ が与えられます。

続く $M$ 行には名所を結ぶ通りが記述されており、$i$ 行目にはその通りによって結ばれている名所の番号を表す、空白で区切られた 2 つの整数 $a_i$ と $b_i$ が与えられます。

出力

空白で区切られた $N$ 個の整数 $c_1, \dots, c_N$ を 1 行に出力してください。ここで $c_i$ ($1 \le c_i \le 4$) は、$i$ 番目の名所の解説を録音すべきナレーターの ID を表します。

解が複数存在する場合は、どれを出力しても構いません。すべてのテストケースにおいて少なくとも 1 つの解が存在すると仮定して構いません。

制約

$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