Background

Translated from Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection) D2T2。$\texttt{3s,0.5G}$。

Problem Description

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$.

Input Format

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 Format

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

3 3
1 2
2 3
3 1
1
1 2

3

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

2
4
4

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

7
5
6
7
-1

Hint

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$。

Translated by ChatGPT 5