Cho một cây (đồ thi liên thông vô hướng không chu trình) gồm \(N\) nút. Các nút được đánh số từ 1 đến \(N\).

Nhiệm vụ của bạn là tô màu các cạnh trên cây, sao cho với mỗi nút, không có hai cạnh bất kì kề với nút đó được tô cùng một màu. Trong các cách tô màu thỏa mãn, hãy tìm cách tô dùng ít màu phân biệt nhất.

Lưu ý: Nếu có nhiều cách tô dùng ít màu phân biệt nhất và thỏa mãn điều kiện, bạn có thể in ra một cách bất kì.

Input

• Dòng đầu tiên gồm một số nguyên \(N (2<N<10^5)\).
• \(N—1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(a_i\) và \(b_i\) \((1<a_i,b_i<N)\) biểu diễn cạnh nối giữa nút \(a_i\) và \(b_i\).

Output

• Dòng đầu tiên in ra một số nguyên \(K\) là số lượng màu phân biệt ít nhất được dùng để tô.
• \(N—1\) dòng tiếp theo, dòng thứ \(i\) in ra một số nguyên \(c_i\) \((1<c_i<K)\) biểu diễn màu của cạnh thứ \(i\) trong cách cho ban đầu.

Example

3
1 2
2 3 

2
1
2

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

4
1
2
3
4
1
1
2

6
1 2
1 3
1 4
1 5
1 6 

5
1
2
3
4
5