Bài toán

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

Nhiệm vụ của bạn là xử lý ~ q ~ truy vấn dạng: khoảng cách giữa hai đỉnh ~ a ~ và ~ b ~ trong cây là bao nhiêu?

Đầu vào

• Dòng đầu tiên chứa hai số nguyên ~ n ~ và ~ q ~: số lượng đỉnh và số truy vấn (~ 1 \leq n, q \leq 2 \cdot 10^5 ~).
• Tiếp theo là ~ n-1 ~ dòng, mỗi dòng chứa hai số nguyên ~ a ~ và ~ b ~: biểu diễn một cạnh giữa hai đỉnh ~ a ~ và ~ b ~.
• Sau đó là ~ q ~ dòng, mỗi dòng chứa hai số nguyên ~ a ~ và ~ b ~: truy vấn khoảng cách giữa hai đỉnh ~ a ~ và ~ b ~.

Đầu ra

• In ra ~ q ~ số nguyên, mỗi số là kết quả của một truy vấn.

Kiểm tra với ví dụ

Input:

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

Output:

1
3
2

Giải thích:

• Khoảng cách giữa ~ 1 ~ và ~ 3 ~ là ~ 1 ~.
• Khoảng cách giữa ~ 2 ~ và ~ 5 ~ là ~ 3 ~.
• Khoảng cách giữa ~ 1 ~ và ~ 4 ~ là ~ 2 ~.