Cho n đỉnh (đánh số thứ tự từ 1 đến n),  m cạnh (mỗi cạnh nối giữa hai đỉnh).

Ban đầu, mỗi đỉnh có một màu riêng biệt, được đánh số là số thứ tự đỉnh đó.

Sau khi nối 2 đỉnh lại với nhau thì 2 đỉnh đó được tô cùng một màu, với màu của đỉnh là đỉnh cha lớn nhất. VD: Nối (1,2) (4,5) và (1,5) thì: đầu tiên nối (1,2) màu của 1 và 2 sẽ là màu 1, tiếp theo nối (4,5) màu của 4 và 5 sẽ là màu 4, cuối cùng nối (1,5) thì màu của 5 sẽ là 1, và vì 5 được nối với 4 ở bước 2, nên 4 cũng được tô thành 1. Lúc đó, các đỉnh 1, 2, 4, 5 đều được tô màu 1, đỉnh 3 không nối với đỉnh nào nên được tô màu 3.

Giữa hai đỉnh mà không có đường đi thì khác màu.

Hỏi màu của mỗi đỉnh sau khi nối một số đỉnh lại với nhau (m cạnh)

Input:

-         Dòng đầu tiên nhập vào số lượng đỉnh (n),

-         Dòng thứ 2 nhập số lượng cạnh (m).

-         m dòng tiếp theo nhập mỗi dòng 2 số, dòng thứ I là chỉ số đầu và cuối của cạnh thứ i.

Output:

Xuất ra 2 dòng.

 - Dòng 1 là các đỉnh (ngăn cách bằng dấu  | ).

 - Dòng 2 là màu tương ứng của các đỉnh thuộc dòng 1 (ngăn cách bởi dấu | )