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$.
The first line contains two integers $1 \le N, M \le 10^5$. The number of nodes and edges of the graph.
The next $M$ lines contain two integers $1 \le a, b \le N, a \ne b$. Each line represents a bidirectional edge in the graph $G$.
The next line contains an integer $1 \le Q \le 10^5$, representing the number of queries to answer.
The next $Q$ lines contain two integers $1 \le a, b \le N, a \ne b$. Each line represents a query in the format described above.