Tý cần giải bài toán sau:

\text{Tổng khoảng cách}

Đị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

Khu rừng FPTOJ có \(N\) ngôi làng và \(N-1\) con đường nối chúng. Hàng năm, mỗi làng tổ chức một lễ hội và mời dân từ tất cả các làng khác đến tham dự. Chi phí đi lại giữa hai làng là khoảng cách giữa chúng. Mỗi làng muốn biết tổng chi phí để mời tất cả mọi người từ các làng khác đến làng mình.

Yêu cầu: Với mỗi đỉnh \(u\), tính tổng khoảng cách từ \(u\) đến tất cả các đỉnh khác trong cây.

Đầu vào

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 2 \times 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa \(u, v\).

Đầu ra

• In ra \(N\) dòng, dòng thứ \(i\) là tổng khoảng cách từ đỉnh \(i\) đến tất cả các đỉnh khác.

Ví dụ

Đầu vào:

4
1 2
2 3
2 4

Đầu ra:

5
3
6
6

Giải thích

• Đỉnh 1: \(1\to2(1)+1\to3(2)+1\to4(2)=5\)
• Đỉnh 2: \(2\to1(1)+2\to3(1)+2\to4(1)=3\)
• Đỉnh 3: \(3\to2(1)+3\to1(2)+3\to4(2)=6\)
• Đỉnh 4: \(4\to2(1)+4\to1(2)+4\to3(2)=6\)

Subtask