Problem Description

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?

Input Format

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 Format

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

5 5 5
1 2
1 4
2 3
2 5
3 4
1 2
4 1
5 3
1 5
2 2

4
3
4
4
5

Hint

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.

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