You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小刘和小吴在玩游戏。

有一张 $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$ 行，每行一个整数，表示询问的答案。

样例 #1

样例输入 #1

3 3
1 2
2 3
3 1
1
1 2

样例输出 #1

3

样例 #2

样例输入 #2

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

样例输出 #2

2
4
4

样例 #3

样例输入 #3

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

样例输出 #3

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