题目背景

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

题目描述

圆和焰在玩游戏。

有一张 $N$ 个节点的无向图，焰会依次向图中添加 $M$ 条边。

焰有 $Q$ 个询问，每次询问给定 $u,v$，问：至少添加前多少条边，才能使得 $u,v$ 间没有割边（换言之，割去任意一条边，都不影响 $u,v$ 的连通性）。特别地，如果 $u,v$ 始终不连通或者始终有割边，则输出 $-1$。

圆准备要去军训了，所以找来了你解决这个问题。

输入格式

第一行，两个整数 $N,M$，含义见题面；

接下来 $M$ 行，第 $i$ 行包含两个整数 $s_i,t_i$，表示第 $i$ 条边为 $(s_i,t_i)$。

第 $(M+2)$ 行，一个整数 $Q$，含义见题面；

接下来 $Q$ 行，每行两个整数 $u,v$，描述一个询问。

输出格式

输出 $Q$ 行，每行一个整数，表示询问的答案。

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

提示

对于 $100\%$ 的数据，保证：

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