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