Cho đơn đồ thị vô hướng, liên thông, không có trọng số bao gồm ~N~ đỉnh và ~M~ cạnh. Các đỉnh được đánh số từ ~1~ đến ~N~ và các cạnh được đánh số từ ~1~ đến ~M~. Yêu cầu xử lý ~Q~ truy vấn, mỗi truy vấn bao gồm hai đỉnh ~u~ và ~v~, yêu cầu tính độ dài đường đi ngắn nhất giữa hai đỉnh này.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ ~(2 \le N \le 10^5~, ~N - 1 \le M \le N+10)~.
• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~a_i~ và ~b_i~ mô tả cạnh thứ ~i~ nối hai đỉnh ~a_i-b_i~ ~(1 \le a_i,b_i \le N)~.
• Dòng tiếp theo chứa số nguyên ~Q~ ~(1 \le Q \le 10^4)~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ mô tả truy vấn ~(1 \le u,v \le N~, ~u \neq v)~.
• Dữ liệu đảm bảo đồ thị đã cho là đơn đồ thị liên thông.

Output

• Với mỗi truy vấn, in ra độ dài đường đi ngắn nhất giữa hai đỉnh ~u~ và ~v~ trên một dòng.

Examples

Sample Input

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

Sample Output

2
2
1

Scoring

• Subtask ~1~ ~-~ ~1000~ điểm: ~N \le 1000~
• Subtask ~2~ ~-~ ~1000~ điểm: ~M = N-1~
• Subtask ~3~ ~-~ ~1000~ điểm: Không có ràng buộc gì thêm

Notes

Trong ví dụ, đồ thị được mô tả trong hình sau: