AT_past202104_o.最短距離クエリ

给定一个有 $N$ 个顶点、$M$ 条边的简单连通无向图。这里 $M \leq N + 10$。
顶点编号为 $1, 2, \dots, N$，边编号为 $1, 2, \dots, M$，第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$。所有边的长度均为 $1$。

请依次处理 $Q$ 个查询。第 $i$ 个查询如下：

• 给定整数 $u_i, v_i$，输出顶点 $u_i$ 和顶点 $v_i$ 之间的最短距离。

输入按以下格式从标准输入给出。

$N$ $M$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_M$ $b_M$
$Q$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_Q$ $v_Q$

请按照题目要求，输出 $Q$ 个整数，每个整数占一行。

注意

本题在 2021 年 4 月 24 日 18:00（日本标准时间）之前禁止讨论。如有讨论，可能会被要求赔偿。考试结束后可以公开总分和认证等级，但请不要透露解答了哪些题目等信息。

数据范围

• 所有输入均为整数。
• $2 \leq N \leq 10^5$
• $N - 1 \leq M \leq N + 10$
• $1 \leq a_i < b_i \leq N$
• 若 $i \neq j$，则 $(a_i, b_i) \neq (a_j, b_j)$
• 给定的图是连通的。
• $1 \leq Q \leq 10^4$
• $1 \leq u_i < v_i \leq N$

样例解释 1

给定的图如下所示。

因此，

• 顶点 $4$ 和顶点 $6$ 之间的最短距离为 $2$；
• 顶点 $1$ 和顶点 $5$ 之间的最短距离为 $4$；
• 顶点 $1$ 和顶点 $2$ 之间的最短距离为 $1$。

由 ChatGPT 4.1 翻译