M 是英国秘密情报局（MI6）中担任关键职务的人员的代号。该职位的核心任务之一是分析敌方通信网络的安全属性。本题描述了 M 每天遇到的典型问题之一。

敌方通信网络由 $N$ 个（看似普通的）邮局和 $M$ 条直接连接某些邮局对的双向道路组成。为方便起见，我们将邮局标记为 $1$ 到 $N$ 的自然数。

当敌人想要从标记为 $a$ 的邮局向标记为 $b$ 的邮局发送秘密信息时，特工会坐上一辆伪装的邮政车辆，沿着连接这两个邮局的某条路径行驶。如果从邮局 $a$ 到邮局 $b$ 的所有路径中都必须经过某条特定的道路，或者这两个邮局之间根本不存在路径，则称邮局对 $(a, b)$ 是“脆弱的”。

M 今天正在分析该网络历史上的脆弱性。具体来说，M 收集了有关网络历史发展的信息，这意味着他知道邮局之间修建道路的顺序。现在，对于某些邮局对，他想知道它们在什么时刻（如果有的话）不再是脆弱的。

输入格式

第一行包含题目描述中的 $N$ 和 $M$。

在接下来的 $M$ 行中，第 $i$ 行包含 $x_i$ 和 $y_i$，表示第 $i$ 条修建的道路连接了标记为 $x_i$ 和 $y_i$ 的邮局（$x_i \neq y_i$）。

可能有多条道路连接同一对邮局。

下一行包含一个自然数 $Q$，表示 M 想要查询的问题数量。

在接下来的 $Q$ 行中，第 $j$ 行包含不同的数字 $a_j$ 和 $b_j$，定义了 M 的第 $j$ 个查询。也就是说，M 想知道邮局对 $(a_j, b_j)$ 在什么时刻不再是脆弱的。

输出格式

在第 $j$ 行输出 M 第 $j$ 个查询的答案。

如果查询中的邮局对仍然是脆弱的，则第 $j$ 个查询的答案为 $-1$。否则，答案是一个自然数 $k$，表示该邮局对在第 $k$ 条道路修建完成后不再是脆弱的。

数据范围

在所有子任务中，满足 $2 \le N \le 300\,000$，$0 \le M \le 300\,000$，$1 \le Q \le 300\,000$。

请注意，在第二个子任务中，前两条道路连接同一对城市，接下来的两条道路连接同一对城市，依此类推。

样例

输入 1

3 3
1 2
2 3
3 1
1
1 2

输出 1

3

输入 2

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

输出 2

2
4
4

输入 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

说明

第三个样例的说明： 考虑第一个查询。在时刻 6（含）之前，邮局 1 和 3 之间要么不存在路径，要么每一条路径都经过道路 1。直到时刻 7 才不再是这种情况。对于第五个查询，邮局 2 和 6 之间从未存在过路径，因此答案为 -1。