Background

Description

In country H, Xiao w decides to travel from city $u$ to city $v$. However, for various reasons, Xiao c is not in city $u$, but Xiao c decides to meet Xiao w somewhere along the way.

Because of the road network in country H, the route Xiao w takes from city $u$ to city $v$ is not fixed. To plan time reasonably, Xiao c wants to know how many cities Xiao w will definitely pass through on all possible routes from city $u$ to city $v$. In particular, $u$ and $v$ must also be counted, which means the answer is never less than $2$.

For various reasons, Xiao c does not know Xiao w’s exact start and end cities, but Xiao c knows there are only $q$ possible pairs of start and end cities. For each of these $q$ possibilities, Xiao c wants to know the number of cities that Xiao w will definitely pass through.

All edges in country H are undirected. Between any two cities, there is at most one direct road. There is no road that connects a city to itself.

At all times, the graph is connected.

Output Format

Output $q$ lines, each containing a single positive integer.

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

3

Hint

From city $1$ to city $5$ there are $4$ possible routes:

$1 \to 2 \to 3 \to 4 \to 5$

$1 \to 2 \to 3 \to 5$

$1 \to 3 \to 4 \to 5$

$1 \to 3 \to 5$

It can be seen that Xiao w will always pass through cities $1, 3, 5$, so the answer is $3$.

You may assume Xiao w will not visit the same city twice. Of course, even if you think revisiting cities is allowed, it does not affect the answer.

Subtask 1: 15 points, $n = 5, q = 50$.

Subtask 2: 15 points, $n = 100, q = 5000$.

Subtask 3: 20 points, $n = 3000, q = 5 \times 10^5$.

Subtask 4: 20 points, $n = 499999, q = 5 \times 10^5, m = n - 1$.

Subtask 5: 30 points, $n = q = 5 \times 10^5$.

Constraints: For all testdata: $1 \leq n \leq 5 \times 10^5, 1 \leq q \leq 5 \times 10^5, 1 \leq m \leq \min(\frac{n(n-1)}{2}, 10^6)$.

Translated by ChatGPT 5