### B - Beyond Connectivity

##### Time & Memory limits:(details)

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

#### 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