在遥远的魔法大陆，xxj 是一名初学的魔法师。 某天魔法学院传来紧急消息：神秘的黑魔法势力准备进攻学院，长老将召回所有学徒。 xxj 此刻距离学院很远，沿途共有m条魔法通道(每个魔法通道两端的节点可以通过传送阵快速到达，代价为1)，和n个节点（包括 xxj 现在所在的位置和学院所在的位置），任意两个节点之间可以通过建立传送阵相连使之变成魔法通道。 xxj 可以临时施展魔法，在任意两个节点之间开通一条新的传送阵（这条传送阵在每次计划中只存在于该计划内，不会永久保留）。 他一共设计了 q 个互相独立的计划，每个计划给出一对节点，表示本次计划要临时开通传送阵的两点。 现在请你帮他计算： 对于每个计划，在仅加入这一条新传送阵后，从节点 1（xxj 所在位置）到节点 n（魔法学院）之间的最少代价是多少。 若仍无法从节点 1 到达节点 n，则输出 -1。

输入格式：

• 第一行包含两个整数 n, m（2 ≤ n ≤ 2×10⁵，0 ≤ m ≤ 2×10⁵）—— 节点数与初始魔法通道数
• 接下来 m 行，每行包含两个整数 u, v（1 ≤ u, v ≤ n）—— 表示一条魔法通道
• 接下来一行包含一个整数 q（1 ≤ q ≤ 10⁵）—— 计划数量
• 接下来 q 行，每行包含两个整数 u, v（1 ≤ u, v ≤ n）—— 表示本次计划中新开通的魔法通道

输出格式：

输出 q 行，每行一个整数：

• 第 i 行为在第 i 次计划中新加入魔法通道 (u, v) 后，从节点 1 到节点 n 的最少代价
• 若无法到达，输出 -1

输入样例1：

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

输出样例1：

2
3
3

样例解释

初始图的最短路径为 1-2-3-5，代价 = 3。

• 第 1 次计划：新增传送阵 (2,5) → 路径 1-2-5，代价= 2
• 第 2 次计划：新增传送阵 (1,4) → 最短路径仍为 1-2-3-5，代价 = 3
• 第 3 次计划：新增传送阵 (4,5) → 最短路径仍为 1-2-3-5，代价 = 3