Tư nhân hóa đường ở Treeland

Một đất nước gồm $n$ thành phố và $n-1$ con đường hai chiều, mỗi con đường nối hai thành phố khác nhau. Từ một thành phố bất kỳ có thể đi đến mọi thành phố còn lại — nghĩa là hệ thống đường tạo thành một cây.

Chính phủ muốn bán toàn bộ các con đường cho các công ty tư nhân. Mỗi con đường được giao cho đúng một công ty, và một công ty có thể sở hữu nhiều con đường.

Một thành phố bị coi là không tốt nếu có một công ty sở hữu từ hai con đường trở lên cùng đi vào thành phố đó. Nói cách khác, thành phố là tốt khi tất cả các con đường nối với nó thuộc về những công ty khác nhau.

Chính phủ muốn chọn một số nguyên $r$ — số lượng công ty tham gia — sao cho có thể giao mỗi con đường cho một công ty trong các công ty được đánh số từ $1$ đến $r$, với số thành phố không tốt không vượt quá $k$. Hãy tìm giá trị $r$ nhỏ nhất thỏa mãn điều kiện này và đưa ra một cách giao đường tương ứng.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$ — số thành phố và số thành phố không tốt tối đa được phép.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i,y_i$ — con đường thứ $i$ nối hai thành phố $x_i$ và $y_i$.

Dữ liệu ra

• Dòng đầu in ra số nguyên $r$ nhỏ nhất tìm được.
• Dòng thứ hai in ra $n-1$ số nguyên $c_1,c_2,\dots ,c_{n-1}$ ($1\le c_i\le r$), trong đó $c_i$ là công ty sở hữu con đường thứ $i$.

Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

• $2\le n\le 2·{10}^5$
• $0\le k\le n-1$
• $1\le x_i,y_i\le n$, các con đường tạo thành một cây.

Ví dụ