Mandatory Cities on Every Route

In country H, little w decides to travel from city \(u\) to city \(v\). However, little c, who isn't at city \(u\) due to various reasons, plans to meet little w along the way. Since the road network in H is such that there can be many possible routes between \(u\) and \(v\), little c is interested in knowing the number of cities that little w must visit no matter which route he takes. In particular, both \(u\) and \(v\) are always included, so the answer is guaranteed to be at least 2.

More formally, for given two distinct cities \(u\) and \(v\) in an undirected connected graph (with no self-loops and at most one edge between any two cities), we say a city is mandatory for the pair \(u, v\) if it appears in every simple path from \(u\) to \(v\) (note that \(u\) and \(v\) are always counted as mandatory). You are given \(q\) candidate pairs of cities \((u, v)\); for each candidate, output the number of mandatory cities.

Note: A city \(x\) (where \(x \neq u, x \neq v\)) is mandatory for \(u, v\) if and only if, after removing \(x\) from the graph, there is no path from \(u\) to \(v\). Equivalently, in terms of the graph's biconnected components, if \(u\) and \(v\) lie in the same biconnected component then only \(u\) and \(v\) are mandatory, otherwise every articulation point on the unique path in the block tree between the components containing \(u\) and \(v\) is mandatory.

It is guaranteed that the graph is connected at all times.

inputFormat

The first line contains two integers \(n\) and \(m\) \( (2 \leq n, m \leq \text{constraints})\), representing the number of cities and roads respectively.

The next \(m\) lines each contain two integers \(a\) and \(b\) representing an undirected road between cities \(a\) and \(b\). There is at most one road between any two cities and no road connects a city to itself.

The next line contains an integer \(q\) \( (q \ge 1)\), representing the number of candidate pairs.

Each of the following \(q\) lines contains two integers \(u\) and \(v\) (\(u \neq v\)), representing a candidate start and end city.

outputFormat

For each candidate pair, output on a separate line a single integer, representing the number of cities that are mandatory on every simple path from \(u\) to \(v\).

sample

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

4
2