题目描述

给你一张 $n$ 个点 $m$ 条边的无向图。现在有一枚棋子初始在点 $x$。双人博弈，先后手轮流移动棋子，每次可以将棋子移动到图上任意一个「与当前棋子所在结点有边直接相连」的结点。保证每个结点都有至少一条边与之相连。

有一初值为 $0$ 的变量 $v$，每次移动过后，记当前棋子所在结点编号为 $t$，则将 $v$ 赋值为 $\max(v,t)$。也就是说，$v$ 的值是棋子移动到过的结点编号最大值且棋子的初始位置 $x$ 一开始并不计算在内。

现在先后手总共移动 $k$ 次棋子，先手希望最终 $v$ 尽可能大，后手希望最终 $v$ 尽可能小。

共有 $q$ 次询问，每次询问给出 $x,k$，询问假如从 $x$ 开始一次共 $k$ 步的博弈，若双方均采用最优策略，那么最终 $v$ 的值为多少。

输入格式

第一行三个整数 $n,m,q$。

接下来 $m$ 行每行两个整数表示图中的边。

接下来 $q$ 行，每行两个整数 $x,k$。

输出格式

共 $q$ 行，每行一个整数表示此轮博弈中最终 $v$ 的值。

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

提示

样例解释

样例中的图如上。

对于第一个询问，显然先手无法迫使后手移动到 $5$，所以答案 $\le 4$，先手第一步移动到 $4$ 即可达成。

对于第二个询问，先手一步能到达的编号最大的点是 $3$，所以答案是 $3$。

数据范围

本题采用捆绑测试。

特殊性质：保证图的形态为一条链。

对于所有数据，保证 $2\le n\le 2\times 10^5$，$1\le m\le 5\times 10^5$，$1\le q\le 2\times 10^5$，$1\le x,k\le n$。

保证给出的图无重边、无自环，保证对于任意点 $u$ 至少存在一个点 $v$ 使得 $u,v$ 之间存在一条边。