Trong một công ty, các nhân viên được tổ chức theo dạng cây phân cấp, với giám đốc là nhân viên số \(1\). Công ty có \(n\) nhân viên và mỗi nhân viên (trừ giám đốc) đều có một quản lý trực tiếp. Bạn được giao nhiệm vụ kiểm tra mối quan hệ cấp bậc giữa các nhân viên.

Có \(q\) truy vấn, với mỗi truy vấn yêu cầu bạn kiểm tra mối quan hệ giữa hai nhân viên \(u\) và \(v\):

• u có phải là cấp trên (trực tiếp hoặc gián tiếp) của \(v\) hay không?
• v có phải là cấp trên của u hay không?
• Hoặc \(u\) và \(v\) không có quan hệ cấp trên/cấp dưới?

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) - số lượng nhân viên và số lượng truy vấn.
• \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\), biểu diễn một mối quan hệ trực tiếp giữa hai nhân viên \(u\) và \(v\) (người quản lý và nhân viên).
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\), yêu cầu kiểm tra mối quan hệ giữa nhân viên \(u\) và \(v\). Đảm bảo \(u \neq v\).

Dữ liệu ra

• Với mỗi truy vấn, in ra:
• \(1\) nếu \(u\) là cấp trên của \(v\).
• \(2\) nếu \(v\) là cấp trên của \(u\).
• \(0\) trong trường hợp không có quan hệ trực tiếp giữa hai người.

Ràng buộc

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

Input 1

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

Output 1

1
1
0
2
2
0

Input 2

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

Output 2

0
2
1
0
0