Có \(N - 1\) cặp bạn bè trong \(N\) chú bò của nông dân John \((2 \le N \le 2 \times 10^5)\) được đánh số từ \(1\) đến \(N\), tạo thành một đồ thị cây. Những chú bò đang rời trang trại lần lượt để đi chơi trong kì nghỉ. Ngày thứ \(i\), chú bò \(i\) sẽ rời trang trại, sau đó tất cả bạn bè của chú ta mà hiện tại vẫn trong trang trại sẽ trở thành bạn của nhau.

Với mỗi \(i \in [1, N]\), ngay trước khi chú bò \(i\) rời khỏi trang trại, bao nhiêu bộ ba có thứ tự \((a, b, c)\) thoả mãn không có chú bò nào trong ba chú bò \(a, b, c\) đang trong kì nghỉ và \(a\) là bạn của \(b\), \(b\) là bạn của \(c\).

Input

• Dòng đầu tiên là số \(N\).
• \(N - 1\) dòng tiếp theo, mỗi dòng gồm \(2\) số \(u_i\) và \(v_i\) cho biết ban đầu \(u_i\) và \(v_i\) là bạn \((1 \le u_i, v_i \le N)\).

Output

• Đáp án với mỗi \(i \in [1, N]\).

Scoring

• Subtask \(1\): \(N \le 500\).
• Subtask \(2\): \(N \le 5000\).
• Subtask \(3\): Không có thêm ràng buộc

3
1 2
2 3

2
0
0

4
1 2
1 3
1 4

6
6
0
0

5
3 5
5 1
1 4
1 2

8
10
2
0
0