Tý có một hệ thống \(N\) trạm phát sóng được kết nối với nhau bằng \(N - 1\) đường truyền cáp quang. Người ta muốn chọn một trạm làm trung tâm điều phối. Chi phí vận hành khi đặt trung tâm tại trạm \(u\) là tổng khoảng cách từ \(u\) đến tất cả các trạm khác.

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

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

Output:

3

Với mỗi trạm \(u\), hãy tính tổng khoảng cách từ \(u\) đến các trạm còn lại.

Đầu vào:

• Dòng đầu gồm \(N\).
• \(N - 1\) dòng sau, mỗi dòng gồm \(u, v\).

Đầu ra:

• In ra \(N\) số nguyên, số thứ \(u\) là tổng khoảng cách từ trạm \(u\) đến tất cả trạm khác.