Graph Game: Maximizing the Visited Node

You are given an undirected graph with \(n\) vertices and \(m\) edges. A game is played on this graph with a chess piece starting at a vertex \(x\) (note that the initial vertex is not counted toward the score). A variable \(v\) is initialized to 0 and will be updated after every move.

The rules of the game are as follows:

• The chess piece is initially positioned at vertex \(x\), but \(v = 0\) initially.
• Two players take turns moving the chess piece. In each move the piece may be moved to any vertex that is adjacent (i.e. directly connected by an edge) to its current vertex. It is guaranteed that every vertex has at least one adjacent edge.
• After a move, if the chess piece lands at vertex \(t\), the variable is updated as \(v \leftarrow \max(v, t)\). In other words, \(v\) will become the maximum vertex label reached by moves only (the initial vertex is not considered).
• A total of \(k\) moves are made. The first player (who moves first) wishes to maximize the final value of \(v\), while the second player wishes to minimize it.

You are given \(q\) queries. Each query specifies a starting vertex \(x\) and a number of moves \(k\). For each query, assuming both players use optimal strategies, determine the final value of \(v\) after exactly \(k\) moves.

inputFormat

The input begins with a line containing three integers \(n\), \(m\), and \(q\) — the number of vertices, edges, and queries respectively.

Then follow \(m\) lines, each containing two integers \(u\) and \(v\), indicating that there is an undirected edge connecting vertices \(u\) and \(v\).

After that, there are \(q\) lines, each containing two integers \(x\) and \(k\), representing the starting vertex and the total number of moves for that query.

outputFormat

For each query, output a single integer — the final value of \(v\) after \(k\) moves, assuming optimal play by both players.

sample

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

4
4
4