Cũng trong dịp kỷ niệm 1 năm ngày yêu, duong3982 đã có một chuyến du lịch cùng với noodles0428 tới quốc gia X.

Quốc gia X có ~n~ thành phố, với ~n - 1~ con đường hai chiều kết nối các thành phố với nhau. Các con đường đảm bảo tính liên thông giữa mọi cặp thành phố trong quốc gia.

Nhằm lên kế hoạch cho chuyến đi, duong3982 có ~Q~ giả định, mỗi giả định bao gồm hai số nguyên dương ~x~ và ~y~ với ý nghĩa: Nếu quốc gia X xây thêm một con đường (~x, y~), thì sẽ có thêm bao nhiêu cặp thành phố có đường đi ngắn hơn đường đi trên hiện trạng ban đầu của thành phố? Lưu ý, việc thêm một con đường chỉ là giả định, hay các truy vấn chỉ áp dụng lên trạng thái ban đầu của các thành phố.

INPUT

Dòng đầu tiên chứa ba số nguyên dương ~n~, ~q~ (~1 \le n, q \le 10^5~).

~n - 1~ dòng tiếp theo, mỗi dòng bao gồm hai số nguyên dương ~u~ và ~v~ (~1 \le u, v \le n~, ~u \neq v~) thể hiện các con đường.

~q~ dòng tiếp theo, mỗi dòng bao gồm hai số nguyên dương ~x~ và ~y~ (~1 \le x, y \le n~, ~x \neq y~) thể hiện một câu hỏi của duong3982.

Vì kinh phí của duong3982 có hạn, nên tổng khoảng cách từ ~x~ tới ~y~ trên mọi truy vấn sẽ không vượt quá ~5 \times 10^6~.

OUTPUT

In ra ~q~ dòng, mỗi dòng là kết quả của một câu hỏi.

SAMPLE INPUT 1

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

SAMPLE OUTPUT 1

10
4

SUBTASKS