P11801 【MX-X9-T5】『GROI-R3』Star Trip

对于整数序列 $p_1,\ldots,p_n$，我们称 $p_i$ 是一个**前缀最大值**当且仅当不存在 $1\le j

第一行，三个正整数 $n,m,q$。 接下来 $m$ 行，每行两个正整数 $u,v$，表示一条连接点 $u, v$ 的边。 接下来 $q$ 行，每行两个正整数 $s,t$，表示一组询问。

$q$ 行，每行一个正整数，表示对应询问的答案。

**【样例解释 #1】** 样例的图如下：  - 对于询问 $2,7$，其中一条权值最小的路径是 $(2,1,8,3,6,7)$，权值为 $2$。 - 对于询问 $4,3$，其中一条权值最小的路径是 $(4,3)$，权值为 $1$。 - 对于询问 $5,4$，其中一条权值最小的路径是 $(5,2,6,3,4)$，权值为 $2$。 - 对于询问 $3,8$，其中一条权值最小的路径是 $(3,8)$，权值为 $2$。 **【数据范围】** **本题采用捆绑测试。** | 子任务编号 | $n,m\le$ | $q\le$ | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | :----------: | :----------: | | 1 | $8$ | $8$ | | $5$ | | 2 | $300$ | $300$ | | $15$ | | 3 | $3000$ | $3000$ | | $10$ | | 4 | $3000$ | $2\times 10^5$ | | $5$ | | 5 | $2\times 10^5$ | $2\times 10^5$ | A | $20$ | | 6 | $2\times 10^5$ | $2\times 10^5$ | B | $20$ | | 7 | $2\times 10^5$ | $2\times 10^5$ | | $25$ | - 特殊性质 A：保证 $m=n-1$。 - 特殊性质 B：保证对于任意 $i\in[1,n]$ 满足 $V'=\{1,2,\ldots,i\}$ 的导出子图是连通图。 对于 $100\%$ 的数据，保证 $1\le n,m,q\leq 2\times 10^5$，$1\le u,v,s,t\le n$，保证图连通，不保证图不存在重边或自环。