Cho một cây gồm ~n~ đỉnh.

Gọi ~f(u, v)~ là khoảng cách ngắn nhất giữa ~u~ và ~v~ (số cạnh trên đường đi đơn). Cho ~q~ truy vấn, mỗi truy vấn có dạng ~(u, v)~ — hãy đếm số đỉnh ~x~ thỏa mãn ~f(u, x) = f(v, x)~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ — có một cạnh nối ~u~ và ~v~.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ — một truy vấn.

Kết quả

In ra ~q~ dòng, dòng thứ ~i~ là đáp án cho truy vấn thứ ~i~.

Ví dụ

Đầu vào:

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

Đầu ra:

2
1
0

Giải thích: Với ~(1, 4)~, hai đỉnh ~2~ và ~5~ cách đều cả ~1~ và ~4~. Với ~(5, 6)~, chỉ có đỉnh ~1~. Với ~(3, 7)~, khoảng cách giữa hai đỉnh là ~1~ — một số lẻ — nên không có đỉnh nào cách đều cả hai.

Giới hạn

• ~1 \le n, q \le 10^5~
• ~1 \le u, v \le n~

Nếu khoảng cách giữa ~u~ và ~v~ là số lẻ thì đáp án luôn bằng ~0~. Nếu ~u = v~ thì mọi đỉnh đều thỏa mãn, đáp án là ~n~.