|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
You are given a non-connected graph G consisting of N nodes and M edges. A graph is said to be non-connected if it is possible to find at least one pair of nodes such that no path in the graph has those nodes as endpoints.
Your task is to answer Q queries. In each query you are given two integers a and b , and you need to compute the length (in edges) of the shortest path between nodes a and b in the complement of G . The complement of a graph G is another graph G′ that doesn't contain any of the edges present in G and contains all the edges not present in G .
Input
The first line contains two integers 1≤N,M≤105 . The number of nodes and edges of the graph.
The next M lines contain two integers 1≤a,b≤N,a≠b . Each line represents a bidirectional edge in the graph G .
The next line contains an integer 1≤Q≤105 , representing the number of queries to answer.
The next Q lines contain two integers 1≤a,b≤N,a≠b . Each line represents a query in the format described above.
Output
For each of the Q queries, print an integer value representing the length (in edges) of the shortest path between the nodes a and b in the complement graph of G .
Sample test(s)
Input
5 3
1 2
2 3
4 5
4
1 2
2 3
3 4
4 5
Output
2
2
1
2