Trong chiến lược phát triển kinh tế của Việt Nam, chính phủ có những chính sách phát triển thành phố Đà Nẵng trở thành một trong những trung tâm tài chính kinh tế và logictis lớn nhất cả nước. Đối với logistics, hạ tầng giao thông là vấn đề quan trọng cần đầu tư xây dựng để kết nối giữa các khu công nghiệp.

Thành phố hiện có ~n~ khu công nghiệp được đánh số từ ~1~ đến ~n~ và ~m~ con đường hai chiều được đánh số từ ~1~ đến ~m~. Mỗi con đường nối hai khu công nghiệp khác nhau. Hai khu công nghiệp bất kì có thể được nối với nhau bằng một (trực tiếp) hoặc nhiều (gián tiếp) con đường.

Đường trọng yếu là con đường duy nhất vận chuyển hàng hóa giữa hai khu công nghiệp, nếu không tồn tại thì việc vận chuyển không được thông suốt.

Yêu cầu: Hãy cho biết việc vận chuyển hàng hóa từ khu công nghiệp ~x~ đến khu công nghiệp ~y~ qua bao nhiêu tuyến đường trọng yếu.

Input

• Dòng đầu tiên chứa hai số nguyên ~n, m~ ~(2 \le n \le 10^5, 1 \le m \le 10^5)~ là số khu công nghiệp và số con đường;

• Dòng thứ ~i~ trong ~m~ dòng tiếp theo chứa hai số nguyên ~u_i, v_i~ ~(1 \le u_i, v_i \le n; u_i \ne v_i)~ mô tả một con đường nối hai khu công nghiệp ~u_i~ và ~v_i~;

• Dòng tiếp theo chứa một số nguyên ~k~ ~(1 \le k \le 10^5)~ là số lượng yêu cầu;

• Dòng thứ ~i~ trong ~k~ dòng tiếp theo chứa hai số nguyên ~s_i, l_i~ ~(1 \le s_i, l_i \le n)~ là việc vận chuyển hàng hóa từ khu công nghiệp ~s_i~ đến khu công nghiệp ~l_i~.

Output

Gồm ~k~ dòng, dòng thứ ~i~ chứa số nguyên ~d_i~ ~(d_i \ge 0)~ là số đường trọng yếu tương ứng yêu cầu thứ ~i~.

Scoring

Sample Input 1

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

Sample Output 1

3
2
3
0

Notes

Nếu một trong ba con đường ~(2, 3)~, ~(3, 4)~ hoặc ~(5, 6)~ gặp sự cố thì việc vận chuyển hàng hóa sẽ bị gián đoạn. Các con đường còn lại nếu có sự cố thì vẫn không ảnh hưởng đến việc vận chuyển giữa khu công nghiệp ~2~ và ~6~. Vì vậy số đường trọng yếu từ khu công nghiệp số ~2~ đến số ~6~ là ~3~.