Số đỉnh chung

Cho một cây có \(n\) đỉnh, được đánh số từ \(1\) đến \(n\). Nhiệm vụ của bạn là xử lý \(q\) truy vấn. Mỗi truy vấn yêu cầu tính số lượng đỉnh chung giữa hai đường đi trong cây.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \leq n \leq 2 \times 10^5, 1 \le q \le 10^5)\) -- số đỉnh của cây và số lượng truy vấn.
• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\) \((1 \leq a, b \leq n)\) -- biểu thị một cạnh nối giữa hai đỉnh \(a\) và \(b\).
• \(q\) dòng cuối cùng mô tả các truy vấn, mỗi truy vấn có dạng A B C D, \((1 \leq A, B, C, D \leq n)\). Yêu cầu: Tìm số lượng đỉnh chung giữa đường đi từ \(A\) đến \(B\) và đường đi từ \(C\) đến \(D\).

Output

• Với mỗi truy vấn, in ra một số nguyên trên một dòng duy nhất biểu thị số lượng đỉnh chung giữa hai đường đi được chỉ định.

Example

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

1

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

0
4
0
3