P10953 An Inescapable Road

In modern society, roads are essential. There are $n$ towns and $m$ roads. Any two towns are connected by roads, and often by more than one. However, some roads have been poorly maintained for years and are unpleasant to travel. In theory, all roads lead to Rome. If one road is bad, you can just take a detour on other roads. But Xiao Lu found that no matter how you travel from town $a$ to town $b$, there are always some unavoidable roads that you must pass through. He wants you to compute: among all paths from $a$ to $b$, how many roads are unavoidable?

The first line contains $n$ and $m$, separated by spaces. The next $m$ lines each contain two integers $x$ and $y$, separated by spaces, indicating that there is a bidirectional road of length $1$ between towns $x$ and $y$. Line $m+2$ contains $q$. The next $q$ lines each contain two integers $a$ and $b$, separated by spaces, representing one query.

For each query, output a positive integer indicating how many roads must be passed through when traveling from town $a$ to town $b$. Print one answer per line.

$1\le n \le 10^5$，$1\le m \le 2\times 10^5$，$1\le q \le 10^5$ For all testdata, $1 \le x,y,a,b \le n$; for any road, the difference between the indices of its two endpoint towns does not exceed $10^4$; Any two towns are connected by at least one path; the same road will not appear twice; a road’s endpoints will not be the same; the two towns in a query will not be the same. Translated by ChatGPT 5