يرغب القزم رائد الأعمال في بدء مشروع للإرشاد السياحي في فروتسواف. ستُجرى جولاته بواسطة حافلة تجوب المدينة، وكلما مرّت الحافلة بمعلم سياحي مثير للاهتمام، سيُشغَّل وصف مسجل لذلك المعلم عبر النظام الصوتي للحافلة.

أعدّ القزم خريطة تتضمن $N$ معالم، مرقمة من $1$ إلى $N$، و$M$ شوارع ثنائية الاتجاه، يصل كل منها بين زوج من المعالم. ومن الميزات المدهشة في خريطته أن كل معلم يتصل بـ $7$ شوارع على الأكثر. ستكون كل جولة عبارة عن متتالية من $3$ معالم مختلفة، حيث يتصل كل معلمين متتاليين بشارع.

الآن، قبل اختيار الجولات، يحتاج القزم إلى إعداد الأوصاف المسجلة للمعالم وتوظيف رواة محترفين. لا يمكنه تحمل تكلفة توظيف سوى $4$ رواة، ولا يمكنه تسجيل الوصف لكل معلم إلا مرة واحدة فقط باستخدام راوٍ واحد. ومع ذلك، يخشى رائد الأعمال أن يصبح حتى صوت أفضل راوٍ رتيبًا بالنسبة للجمهور، لذلك قرر أنه في أي جولة ممكنة، لا يجوز أن تُروى الأوصاف الـ $3$ جميعها بواسطة الراوي نفسه.

لم يستقر القزم بعد على أي جولة محددة، وحجز استوديو التسجيل الخاص به هو غدًا. ساعده في تعيين الرواة للمعالم بحيث لا يتم سردها كلها بواسطة الراوي نفسه في أي جولة ممكنة.

الإدخال

يحتوي السطر الأول من الإدخال على عددين صحيحين مفصولين بمسافة $N$ و $M$، يمثلان عدد المعالم وعدد الشوارع في خريطة القزم.

تصف الأسطر الـ $M$ التالية الشوارع التي تربط المعالم، حيث يحتوي السطر الـ $i$ على عددين صحيحين مفصولين بمسافة $a_i$ و $b_i$ يمثلان رقمي المعلمين المتصلين بهذا الشارع.

الإخراج

اطبع سطرًا واحدًا يحتوي على $N$ أعداد صحيحة مفصولة بمسافات $c_1, \dots, c_N$، حيث يمثل $c_i$ ($1 \le c_i \le 4$) معرّف الراوي الذي ينبغي أن يسجل وصف المعلم الـ $i$.

إذا كانت هناك عدة حلول، فاطبع أيًا منها. يمكنك افتراض أنه يوجد حل في كل حالة اختبار.

القيود

$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