Hạo nhận được một cây có \(n\) đỉnh. Anh quyết định tô các cạnh của cây đó bằng \(k\) màu khác nhau.

Ban đầu, tất cả các cạnh của cây được tô bằng màu \(0\). Anh sẽ sử dụng các màu theo thứ tự từ màu thứ nhất đến màu thứ \(k\), trong đó anh sẽ sử dụng màu thứ \(i\) để tô tất cả các cạnh trên đường đi ngắn nhất từ nút thứ \(x_i\) đến nút thứ \(y_i\). Nếu một cạnh trên đường đi đó đã được tô, màu mới sẽ ghi đè lên màu cũ.

Hãy giúp Hạo xác định màu cuối cùng của mỗi cạnh.

Dữ liệu vào

• Dòng đầu tiên chứa các số \(n\) và \(k\) \((2 \le n \le 10^6, 1 \le k \le 10^6)\), biểu thị số đỉnh trong cây và số lượng màu.
• Trong \(n - 1\) dòng tiếp theo, có các số \(u_i\) và \(v_i\) \((1 \le u_i, v_i \le n)\) - cạnh thứ i nối các đỉnh \(u_i\) và \(v_i\). Đảm bảo rằng các cạnh tạo thành một cây.
• Trong \(k\) dòng tiếp theo, có các số \(x_i\) và \(y_i\) \((1 \le x_i, y_i \le n)\), biểu thị các nút mà giữa chúng Hạo tô các cạnh.

Dữ liệu ra

• Trên một dòng duy nhất, in ra màu cuối cùng của mỗi cạnh theo thứ tự chúng được cho trong input.

Chấm điểm

Input 1

6 2
1 2
2 3
2 4
1 5
4 6
5 2
6 1

Output 1

2 0 2 1 2

Input 2

5 4
1 2
2 3
3 4
4 5
5 5
4 3
2 1
2 4

Output 2

3 4 4 0

Input 3

5 4
3 5
2 3
4 3
5 1
4 1
5 5
4 2
1 5

Output 3

1 3 3 4

Giải thích ví dụ đầu tiên: Với màu đầu tiên, anh tô các cạnh 1 và 4, sau đó với màu thứ hai, anh tô các cạnh 1, 3 và 5.