คนแคระผู้ประกอบการต้องการเริ่มต้นธุรกิจนำเที่ยวในเมืองวรอตสวัฟ ทัวร์ของเขาจะดำเนินการโดยรถบัสที่ขับผ่านเมือง และเมื่อใดก็ตามที่รถบัสแล่นผ่านสถานที่สำคัญที่น่าสนใจ เสียงบรรยายที่บันทึกไว้ของสถานที่สำคัญนั้นก็จะถูกเปิดผ่านระบบเครื่องเสียงของรถบัส

คนแคระได้เตรียมแผนที่ซึ่งประกอบด้วยสถานที่สำคัญ $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