Cho một cây \(n\) đỉnh. Định nghĩa \(f(u,v)\) là khoảng cách ngắn nhất giữa \(u\) và \(v\). Cho \(q\) truy vấn dạng \((u,v)\), đếm số lượng đỉnh \(x\) sao cho: \(f(u,x)=f(v,x)\)

Dữ liệu vào

• Dòng đầu tiên gồm \(2\) số nguyên \(n,q\)
• \(n-1\) dòng tiếp theo, mỗi dòng gồm \(2\) số nguyên \(u,v\) thể hiện cạnh nối \(u\) và \(v\).
• \(q\) dòng tiếp theo, mỗi dòng gồm \(2\) số nguyên \(u,v\) một truy vấn.

Dữ liệu ra

• In ra \(q\) số nguyên, đáp án của \(q\) truy vấn.

Điều kiện

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

Input 1

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

Output 1

2
1
0