P14912 [NHSPC 2024] 海盗地图

在某个大洋中，有 $n$ 座小岛，分别编号从 $\{1, 2, \ldots, n\}$，另外也有着 $m$ 条航线来直接连接两个小岛。每条航线都以一组数字 $x, y$ 表示 ，代表通过这条航线从小岛 $x$ 行船至小岛 $y$ 只需要一单位的时间，反之从小岛 $y$ 行船至小岛 $x$ 也只需要一单位的时间。然而并不是任两个小岛 $x$ 和 $y$ 都有一条航线直接连接，这时要从 $x$ 行船至 $y$，需要通过一系列的小岛作为中间接驳的岛。具体来说，我们需要一系列的小岛 $a_1, a_2, \ldots, a_k$，其中 $x = a_1,y = a_k$，而且对于所有 $1 \leq i \leq k-1$，$a_i$ 和 $a_{i+1}$ 有航线直接相连，这会是一个间接连接小岛 $x$ 和 $y$ 的方式，并且需要花费 $k-1$ 单位的时间。两个小岛之间的最快速行船路线的所需时间为所有能满足上列要求的序列所需花费时间的最小值。并且任意两个小岛都能通过这些航线直接或间接的连接。 另外在每座小岛都有一组海盗占据着，他们各自记录着从他们所在的小岛至各个岛的最快速行船路线的所需时间。由于海盗们十分忙碌，有些需要花费比较长时间的行船路线，会随着时间过去，而忘记确切所需时间。只能确定这些被遗忘的最快速行船路线的所需时间的值**至少严格大于 $\sqrt{n}$。** :::align{center}  图片来源：产生自 ChatGPT ::: 海盗们将航线的完整信息寄给你，并给 $q$ 组被遗忘的路线，希望你帮他们算出这些已忘记的最快速行船路线的所需时间。

$$\begin{aligned} &n \ m \ q \\ &x_1 \ y_1 \\ &x_2 \ y_2 \\ &\vdots \\ &x_m \ y_m \\ &s_1 \ t_1 \\ &s_2 \ t_2 \\ &\vdots \\ &s_q \ t_q \end{aligned}$$ * $n$ 代表小岛数。 * $m$ 代表海盗给出的航线数。 * $q$ 代表忘记所需时间的最快速行船路线数量。 * $x_i, y_i$ 代表有一条航线直接连接着小岛 $x_i$ 和 $y_i$。 * $s_i, t_i$ 代表海盗遗忘的第 $i$ 条路线。

$$\begin{aligned} d_1 \ d_2 \ \ldots \ d_q \end{aligned}$$ * $d_i$ 代表海盗遗忘的第 $i$ 条路线所需的最快速行船时间。

### 数据限制 * $1 \leq n \leq 10^4$。 * $1 \leq m \leq 10^5$。 * $1 \leq q \leq 3\times 10^4$。 * $1 \leq x_i, y_i \leq n,x_i \neq y_i$。 * $1 \leq s_i, t_i \leq n$。 * 保证所有被遗忘的路线皆满足其最快速行船路线的所需时间的值**至少严格大于 $\sqrt{n}$。** * 海盗给出的航线都是相异的。 * 保证任意两个小岛都能通过这些航线直接或间接的连接。 * 输入的数皆为整数。 ### 评分说明 本题共有四组子任务，条件限制如下所示。 每一组可有一或多笔测试数据，该组所有测试数据皆需答对才会获得该组分数。 | 子任务 | 分数 | 额外输入限制 | | :------: | :----: | ------------ | | 1 | 6 | $n \le 500$。 | | 2 | 17 | $n \le 5\times 10^3$，$m \le 10^4$。 | | 3 | 21 | 详见备注（一）。 | | 4 | 56 | 无额外限制。 | 备注（一）：存在至多 $1000$ 个特别小岛，使得所有被遗忘的从小岛 $x$ 至小岛 $y$ 最快速行船路线的所需时间，不是 $x$ 是特别小岛，就是 $y$ 是特别小岛。