P11693 [JRKSJ ExR] 构造字符串使得

给你一张 $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$，所以答案 $\le 4$，先手第一步移动到 $4$ 即可达成。 对于第二个询问，先手一步能到达的编号最大的点是 $3$，所以答案是 $3$。 ### 数据范围 **本题采用捆绑测试。** | $\text{Subtask}$ | $n\le$ | $q\le$|特殊性质| 分数 | |:--:|:--:|:--:|:--:|:--: | $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$ | 特殊性质：保证图的形态为一条链。 对于所有数据，保证 $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$ 之间存在一条边。