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 翻译