P11693 [JRKSJ ExR] Construct a String Such That

You are given an undirected graph with $n$ vertices and $m$ edges. A game piece initially is at vertex $x$. This is a two-player game: the first player and the second player take turns moving the piece. Each move, the player may move the piece to **any** vertex that is **directly connected by an edge** to the vertex where the piece is currently located. It is **guaranteed that every vertex is connected to at least one edge**. There is a variable $v$ with initial value $0$. **After each move**, let $t$ be the index of the vertex where the piece is currently located, and then set $v$ to $\max(v,t)$. In other words, $v$ is the maximum vertex index that the piece has moved to, and **the initial position $x$ is not counted at the beginning**. The two players will move the piece **a total of $k$ times**. The first player wants the final value of $v$ to be as large as possible, while the second player wants the final value of $v$ to be as small as possible. There are $q$ queries. Each query gives $x,k$ and asks: if a game of exactly $k$ moves starts from $x$, and both players use optimal strategies, what will the final value of $v$ be?

The first line contains three integers $n,m,q$. The next $m$ lines each contain two integers describing an edge in the graph. The next $q$ lines each contain two integers $x,k$.

Output $q$ lines. Each line contains one integer, the final value of $v$ in that game.

### Sample Explanation  The graph in the sample is shown above. For the first query, clearly the first player cannot force the second player to move to vertex $5$, so the answer is $\le 4$. The first player can achieve this by moving to vertex $4$ on the first move. For the second query, the largest-index vertex that the first player can reach in one move is $3$, so the answer is $3$. ### Constraints **This problem uses bundled testdata.** | $\text{Subtask}$ | $n\le$ | $q\le$ | Special Property | Score | |:--:|:--:|:--:|:--:|:--:| | $1$ | $5$ | $5$ | | $7$ | | $2$ | $80$ | $80$ | | $14$ | | $3$ | $700$ | $700$ | | $17$ | | $4$ | $2\times 10^5$ | $50$ | | $20$ | | $5$ | $2\times 10^5$ | $2\times 10^5$ | $✓$ | $5$ | | $6$ | $2\times 10^5$ | $2\times 10^5$ | | $37$ | Special property: the graph is guaranteed to be a single chain (a path). For all testdata, it is guaranteed that $2\le n\le 2\times 10^5$, $1\le m\le 5\times 10^5$, $1\le q\le 2\times 10^5$, and $1\le x,k\le n$. It is guaranteed that the given graph has no multiple edges and no self-loops. It is also guaranteed that for any vertex $u$, there exists at least one vertex $v$ such that there is an edge between $u$ and $v$. Translated by ChatGPT 5