题目描述

玛雅帝国曾是当时最强大的势力之一。除此之外，玛雅人在科学和工程方面也极其先进。他们的帝国覆盖了 $N$ 个聚落。

在任意两个聚落之间，玛雅人都修建了一条双向道路，而且每条道路的长度都恰好是 55 英里。至于这是如何做到的，科学家至今仍不清楚。不幸的是，如今其中一部分道路已经成为废墟，无法再使用。由于玛雅工程师实在太有才华，只有 $M$ 条道路已经损坏，其余道路仍然完好无损。

你想知道，对于若干对聚落，只沿着仍然完好的玛雅道路通行时，从一个聚落到另一个聚落的最短路线长度等于多少个 55 英里。

请编写程序 missing.cpp，回答这些问题。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示聚落数量和缺失道路（已成废墟的道路）数量。
接下来 $M$ 行，每行包含两个整数 $A_i$ 和 $B_i$，表示第 $i$ 条缺失道路原本连接的两个聚落编号。
然后一行包含整数 $Q$，表示询问数量。
接下来 $Q$ 行，每行包含两个整数 $C_j$ 和 $D_j$，表示第 $j$ 个询问中的两个聚落编号。

输出格式

对于每个询问，按输入顺序在单独一行输出答案。
如果对应询问不存在任何可行路径，则输出 -1。

数据范围

• $1 \le N \le 10^4$
• $1 \le M \le N^{1.5}$
• $1 \le Q \le 10^6$
• $0 \le A_i, B_i, C_j, D_j < N$

子任务

只有当你的程序通过该子任务中的所有测试时，才能获得对应分数。

样例

输入

6 10
0 2
5 0
4 1
1 3
1 5
2 5
2 4
4 0
5 3
4 5
4
1 4
3 2
4 4
0 5

输出

3
1
0
-1