P10875 [COTS 2022] Game M

Translated from [Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2022/) D2T2。$\texttt{3s,0.5G}$。

There is an undirected graph with $N$ nodes. We add $M$ edges to the graph one by one. There are $Q$ queries. Each query gives $u, v$ and asks: what is the minimum number of first edges that must be added so that there is no bridge on the connection between $u$ and $v$ (in other words, removing any single edge will not affect the connectivity between $u$ and $v$)? In particular, if $u$ and $v$ are always disconnected, or there is always a bridge, output $-1$.

The first line contains two integers $N, M$, as described in the statement. The next $M$ lines: the $i$-th line contains two integers $s_i, t_i$, meaning the $i$-th edge is $(s_i, t_i)$. The $(M+2)$-th line contains an integer $Q$, as described in the statement. The next $Q$ lines: each line contains two integers $u, v$, describing a query.

Output $Q$ lines. Each line contains one integer, the answer to the query.

For $100\%$ of the testdata, it is guaranteed that: - $2\le N \le 3\times 10^5$, $0\le M\le 3\times 10^5$, $1\le Q\le 3\times 10^5$； - $s_i\neq t_i$, $u\neq v$； - $1\le u,v,s_i,t_i\le N$。 | Subtask ID | Score | Constraints | |:-----:|:------:|:-------:| | $1$ | $10$ | $Q=1$ | | $2$ | $20$ | $2\mid M$，$(s_{2i-1},t_{2i-1})=(s_{2i},t_{2i})$ | | $3$ | $30$ | $N,M\le 5\, 000$ | | $4$ | $40$ | No additional constraints. | Translated by ChatGPT 5