Đấ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ố với nhau 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 \leq 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.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên \(n\),\(m\)(\(1 \leq n \leq 5000\),\(\ n - 1 \leq m \leq \min\left( \frac{n(n - 1)}{2},5000 \right)\)) 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 \leq u,\ v \leq 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 \leq q \leq 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 \leq s,\ t \leq 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.

Kết quả:

+ 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\).

Ràng buộc:

• \(20\%\) số tests tương ứng với 2\(0\%\) số điểm của bài có: \(q \leq 1000,s\ + \ 1 = t\) với mọi lựa chọn;

• \(20\%\) số tests khác tương ứng với 2\(0\%\) số điểm của bài có: \(n \leq 1000,\ \ q \leq 1000\);

• \(20\%\) số tests khác tương ứng với \(20\%\) số điểm của bài có: \(n \leq 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.

Ví dụ: