P11801 [MX-X9-T5] "GROI-R3" Star Trip

For an integer sequence $p_1,\ldots,p_n$, we call $p_i$ a **prefix maximum** if and only if there does not exist $1\le j

The first line contains three positive integers $n,m,q$. The next $m$ lines each contain two positive integers $u,v$, representing an edge connecting vertices $u$ and $v$. The next $q$ lines each contain two positive integers $s,t$, representing a query.

Output $q$ lines, each containing one positive integer, denoting the answer to the corresponding query.

**[Sample Explanation #1]** The sample graph is as follows:  - For the query $2,7$, one path with minimum weight is $(2,1,8,3,6,7)$, and its weight is $2$. - For the query $4,3$, one path with minimum weight is $(4,3)$, and its weight is $1$. - For the query $5,4$, one path with minimum weight is $(5,2,6,3,4)$, and its weight is $2$. - For the query $3,8$, one path with minimum weight is $(3,8)$, and its weight is $2$. **[Constraints]** **This problem uses bundled testdata.** | Subtask ID | $n,m\le$ | $q\le$ | Special Property | Score | | :----------: | :----------: | :----------: | :----------: | :----------: | | 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$ | - Special Property A: It is guaranteed that $m=n-1$. - Special Property B: It is guaranteed that for any $i\in[1,n]$, the induced subgraph with $V'=\{1,2,\ldots,i\}$ is connected. For $100\%$ of the testdata, it is guaranteed that $1\le n,m,q\leq 2\times 10^5$, $1\le u,v,s,t\le n$. The graph is guaranteed to be connected, but it is not guaranteed that there are no multiple edges or self-loops. Translated by ChatGPT 5