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.

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

Input

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

Output

2
2
1
2