分数: 6 点
警告
2021 年 4 月 24 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。
问题陈述
给定一个简单的连通无向图,其中 M ≤ 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.
约束
- 输入中的所有值都是整数。
- 2 ≤ N ≤ 10^5
- N - 1 ≤ M ≤ N + 10
- 1 ≤ a_i < b_i ≤ N
- (a_i, b_i) ≠ (a_j, b_j) 为 i ≠ j
- 给定的图形已连接。
- 1 ≤ Q ≤ 10^4
- 1 ≤ u_i < v_i ≤ N
输入
输入由标准输入按以下格式给出:
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 按问题描述指定的整数,每个整数占一行。
示例输入 1
7 6 1 2 2 3 3 4 4 5 5 6 6 7 3 4 6 1 5 1 2
示例输出 1
2 4 1
给出的图表如下:

因此,
- 顶点之间的最短距离 4 和顶点 6 is 2;
- 顶点之间的最短距离 1 和顶点 5 is 4;
- 顶点之间的最短距离 1 和顶点 2 is 1.
示例输入 2
8 8 1 6 6 7 2 5 2 3 1 8 1 5 5 6 4 8 8 4 6 1 3 1 4 4 7 5 6 6 7 1 8 3 7
示例输出 2
3 3 2 4 1 1 1 4
示例输入 3
11 12 6 10 9 10 8 11 3 5 1 8 7 9 2 6 3 6 4 7 3 10 1 7 1 2 6 7 10 3 8 4 7 5 9 4 5 5 10
示例输出 3
2 4 1 3 5 2