Trong lớp ITK20 có \(n\) bạn học sinh, được đánh số từ \(1\) đến \(n\), mỗi bạn đều có một màu yêu thích. Các màu sắc có thể được đại diện bởi các số nguyên từ \(1\) đến \(n\).

Tồn tại \(m\) cặp học sinh \((a,\ b)\) sao cho học sinh \(b\) ngưỡng mộ học sinh \(a\). Có thể xảy ra trường hợp \(a=b\), nghĩa là bạn học sinh này ngưỡng mộ chính bản thân mình. Với mỗi màu sắc c, nếu hai học sinh \(x,\ y\) cùng ngưỡng mộ một bạn học sinh thích màu này, thì cả hai bạn \(a\) và \(b\) thích chung một màu (không nhất thiết là màu c).

Xác định cách chọn màu yêu thích cho mỗi học sinh sao cho thỏa dữ liệu đầu vào, đồng thời số màu khác nhau được yêu thích của các học sinh trong cả lớp phải lớn nhất. Nếu có nhiều cách chọn thỏa mãn, in ra cách chọn nhỏ nhất theo thứ tự từ điển.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(m\ (1\leq n,\ m\leq2\times10^5)\);
• Tiếp theo là \(m\) dòng, mỗi dòng gồm hai số nguyên dương \(a\) và \(b\ (1\leq a,\ b\leq n)\) ghi cách nhau bởi dấu cách, thể hiện học sinh \(b\) ngưỡng mộ học sinh \(a\). Mỗi cặp \((a,\ b)\) có thể xuất hiện nhiều hơn một lần trong bộ dữ liệu.

Output

• Với mỗi học sinh, in ra màu yêu thích của học sinh đó trên một dòng.

Ví dụ

Sample input

9 12
1 2
4 2
5 8
4 6
6 9
2 9
8 7
8 3
7 1
9 4
3 5
3 4

Sample output

1
2
3
1
1
2
3
2
3

Note

Trong đồ thị dưới đây, những đỉnh được in đậm viền biểu diễn những học sinh có màu yêu thích là \(1\).

Ràng buộc

• \(30\%\) số test có \(1\leq n,\ m\leq10^3\);
• \(70\%\) số test còn lại không có ràng buộc gì thêm.