Cho một đồ thị dạng cây với ~N~ đỉnh và ~N-1~ cạnh. Hằng ngày có một chú khỉ đi từ một đỉnh ~a~ đến đỉnh ~b~. Chú thấy rằng có một số đỉnh đã được thăm vào các ngày trước đó. Chú băn khoăn là trên đường đi ngày hôm nay từ ~a~ đến ~b~ có bao nhiêu đường đi của các ngày trước đó giao với ngày hôm nay, hai đường giao nhau là 2 đường có ít nhất một đỉnh chung.

Input

Vào từ file WALKING.INP:

• Dòng đầu ghi số ~N, Q\ (1 \le N, Q \le 10^5)~ là số đỉnh và số ngày dạo chơi.
• ~N-1~ dòng tiếp ghi cặp số ~(u, v)\ (1 \le u, v \le N)~ mô tả cạnh của cây.
• ~Q~ dòng tiếp theo mô tả truy vấn, mỗi dòng chứa bộ số ~(a,b)\ (1 \le a,b \le N)~ thể hiện lộ trình dạo chơi của các ngày.

Output

Ghi ra tệp WALKING.OUT:

• ~Q~ dòng, trong đó dòng thứ ~i~ là số ngày có khác nhau đã từng đi qua một đỉnh trên lộ trình của ngày ~i~.

Sample Input 1

5 4
1 2
1 3
3 4
3 5
4 5
4 2
1 3
1 2

Sample Output 1

0
1
2
2

Giải thích