Du lịch

Đất nước ABC có \(n\) thành phố, các thành phố được đánh số từ \(1\) đến \(n\) và các con đường nối giữa các thành phố là đường đi hai chiều. Hệ thống giao thông đó đảm bảo luôn đi được từ một thành phố bất kỳ đến một thành phố khác thông qua các đường đi.

Nam đang dự định đi du lịch đất nước ABC, chuyến đi của cậu bắt đầu từ thành phố \(s\) và kết thúc tại thành phố \(t\). Nam có thể di chuyển tự do giữa các thành phố và cậu có thể thăm lại thành phố mà cậu đã thăm với số lần tùy thích, nhưng nếu đến thành phố \(t\) thì Nam sẽ kết thúc hành trình của mình. Nam sẽ chụp một bức ảnh ở thành phố đầu tiên của chuyến đi nếu \(s \le t\). Sau đó, mỗi khi cậu đến một thành phố có chỉ số lớn hơn tất cả thành phố đã được thăm, cậu sẽ chụp thêm một bức ảnh ở thành phố đó. Đồng thời, Nam cũng muốn chụp một bức ảnh ở thành phố kết thúc nếu nó thỏa mãn điều kiện chụp ảnh trên.

Yêu cầu: Nam có \(q\) lựa chọn, mỗi lựa chọn cho biết thành phố xuất phát \(s\) và thành phố kết thúc \(t\). Bạn hãy cho biết số lượng ảnh tối đa cậu ấy có thể chụp trong suốt chuyến đi từ \(s\) đến \(t\), hoặc không có hành trình nào với điều kiện như vậy.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, m\) (\(1 \le n \le 5000\), \(n-1 \le m \le \min(\frac{n(n-1)}{2}, 5000)\)) lần lượt là số thành phố ở đất nước ABC và số con đường nối các thành phố.
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u, v\) (\(1 \le u, v \le n\)) thể hiện một đường đi hai chiều nối hai thành phố \(u\) và \(v\).
• Dòng tiếp theo chứa số nguyên \(q\) (\(1 \le q \le 2 \times 10^5\)) là số lựa chọn của Nam.
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(s, t\) (\(1 \le s, t \le n\)) thể hiện một lựa chọn của Nam.

Các số trên một dòng ghi cách nhau bởi dấu cách.

Output

• Gồm \(q\) dòng, theo thứ tự lựa chọn của Nam trong tệp dữ liệu vào, mỗi dòng ghi một số là số lượng bức ảnh lớn nhất mà Nam chụp được trong hành trình lựa chọn đó. Nếu không có hành trình như vậy thì ghi ra \(-1\).

Example

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

2
2
-1
1

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

4
-1

3 2
1 3
3 2
2
1 1
1 2

1
-1

Scoring

• 20% số tests tương ứng với 20% số điểm của bài có: \(q \le 1000, s+1 = t\) với mọi lựa chọn.
• 20% số tests khác tương ứng với 20% số điểm của bài có: \(n \le 1000, q \le 1000\).
• 20% số tests khác tương ứng với 20% số điểm của bài có: \(n \le 1000\).
• 40% số tests còn lại tương ứng với 40% số điểm của bài không có ràng buộc gì thêm.