הגמד היזם רוצה להקים עסק להדרכת תיירים בוורוצלב. הסיורים שלו ייערכו באמצעות אוטובוס שייסע ברחבי העיר, ובכל פעם שהאוטובוס יעבור ליד אתר מעניין, תיאור מוקלט של אותו אתר יושמע במערכת הכריזה של האוטובוס.

הגמד הכין מפה הכוללת $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