Khu công nghiệp ~XYZ~ có ~N~ công ty. Các công ty này thể hiện mức độ hợp tác với nhau trong hoạt động sản xuất kinh doanh thông qua hai kí hiệu ở phần trên và phần dưới trong bảng ghi nhớ hợp tác của công ty. Hai công ty có quan hệ hợp tác trực tiếp nếu có cùng kí hiệu ở phần trên hoặc có cùng kí hiệu ở phần dưới. Hai công ty ~c_0~ và ~c_f~ có quan hệ hợp tác gián tiếp nếu có cùng một chuỗi các công ty ~c_1,...,c_{f - 1}~ trong đó ~c_k~ có quan hệ trực tiếp với ~c_{k + 1}~ ~(0 \le k < f)~. Nếu ~c_0~ và ~c_f~ là khác nhau và có quan hệ hợp tác trực tiếp hoặc gián tiếp thì ta nói mức độ hợp tác của hai công ty là ~f~, với ~f~ nhỏ nhất có thể.

Cho ~q~ truy vấn, mỗi truy vấn có dạng ~x~ ~y~: xác định mức độ hợp tác của công ty ~x~ và công ty ~y~.

Yêu cầu: Với mỗi truy vấn được cho, hãy xác định mức độ hợp tác của hai công ty.

Dữ liệu vào

Từ tập tin văn bản FRIENDSHIP.INP gồm:

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~S~ ~(2 \le N \le 90000, 2 \le S \le 300)~ là số lượng công ty và số lượng kí hiệu có thể xuất hiện trong bảng ghi nhớ của công ty.
• Dòng thứ ~i~ trong ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~t_i~ và ~b_i~ ~(1 \le t_i, b_i \le S)~, ~t_i~ là số nguyên đại diện cho kí hiệu ở phần trên và ~b_i~ là số nguyên đại diện cho kí hiệu ở phần dưới trong bảng ghi nhớ của công ty thứ ~i~. Nếu ~i \ne j~ thì ~t_i \ne t_j~ hoặc ~b_i \ne b_j~.
• Dòng tiếp theo chứa số nguyên ~q~ ~(1 \le q \le 10^5)~, là số lượng truy vấn.
• Mỗi dòng trong ~q~ dòng tiếp theo chứa hai số nguyên ~x~ và ~y~ ~(1 \le x, y \le N,x \ne y)~, là hai công ty cần xác định mức độ hợp tác.

Các số trên cùng một dòng cách nhau ít nhất một dấu cách.

Dữ liệu ra

Ghi ra file văn bản FRIENDSHIP.OUT gồm ~q~ dòng: Dòng thứ ~i~ ghi ra một số nguyên thể hiện mức độ hợp tác của hai công ty trong truy vấn thứ ~i~. Nếu hai công ty không có quan hệ hợp tác thì ghi ~-1~.

Ví dụ

Dữ liệu

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

Kết quả

1
1
2
-1

Giải thích

Ví dụ trên có ~4~ truy vấn:

• Trong truy vấn thứ ~1~, công ty ~1~ ~(c_0)~ có quan hệ hợp tác trực tiếp với công ty ~2~ ~(c_1)~ do hai công ty có cùng kí hiệu ở phần dưới trong bảng ghi nhớ nên mức độ hợp tác của hai công ty này là ~1~. Kết quả truy vấn ghi ~1~.
• Trong truy vấn thứ ~2~, công ty ~2~ ~(c_0)~ có quan hệ hợp tác trực tiếp với công ty ~3~ ~(c_1)~ do hai công ty có cùng kí hiệu ở phần trên trong bảng ghi nhớ nên mức độ hợp tác của hai công ty này là ~1~. Kết quả truy vấn ghi ~1~.
• Trong truy vấn thứ ~3~, công ty ~1~ ~(c_0)~ có quan hệ hợp tác trực tiếp với công ty ~2~ ~(c_1)~, công ty ~2~ ~(c_1)~ có quan hệ hợp tác trực tiếp với công ty ~3~ ~(c_2)~. Do đó, mức độ hợp tác của hai công ty này là ~2~. Kết quả truy vấn ghi ~2~.
• Trong truy vấn thứ ~4~, hai công ty ~1~ và ~4~ không có quan hệ hợp tác nên mức độ hợp tác của hai công ty này là ~-1~. Kết quả truy vấn ghi ~-1~.