平稳套服裁

题目描述

橙子在游戏中建立了 $n$ 个城市，并且在城市间建立了 $m$ 条双向道路，使得所有城市可以互相到达，但是一场地震摧毁了所有道路。在地震后的 $m$ 天里，第 $i$ 天连接 $u_i,v_i$ 的道路会被修复，但是由于道路比较窄，只允许单向通行，橙子可以为每条修复的道路决定通行方向。

为了评估修复情况，橙子会问你 $q$ 个问题，每个问题给定 $u,k$，你需要告诉她：所有在第 $k$ 天存在一种定向方案使得 $u$ 能到达的城市中，至少在第几天，存在一种定向方案，使得这些城市两两间可以互相到达；特别地，如果这样的点只有一个，输出 $0$，如果永远不能满足条件，输出 $m+1$。

输入格式

第一行 $3$ 个整数 $n,m,q$，分别表示城市数量、道路数量、询问个数。

接下来 $m$ 行，每行 $2$ 个整数 $u_i,v_i$，表示第 $i$ 天被修复的道路。

接下来 $q$ 行，每行 $2$ 个整数 $u,k$，表示一组询问。

输出格式

$q$ 行，每行一个整数表示询问的答案。

样例输入 1

6 8 5
1 2
1 3
2 3
1 4
1 5
2 5
3 4
1 6
1 1
4 1
1 4
5 5
6 8

样例输出 1

3
0
7
7
9

样例解释

对于第 $1$ 组询问，城市 $1$ 在加入第 $1$ 条边之后可以到达的城市有 $1,2$，在第 $3$ 时刻，将道路定向为 $1\to2,2\to3,3\to1$ 后，两两间互相到达。

对于第 $2$ 组询问，城市 $4$ 在加入第 $1$ 条边之后可以到达的城市只有 $4$，根据题目应该输出 $0$。

对于第 $5$ 组询问，城市 $6$ 在加入第 $8$ 条边之后可以到达的城市有 $1,2,3,4,5,6$，可以发现永远不能满足条件，根据题目应该输出 $m+1=9$。

转换注：原文将样例输出标题误写为“样例输入 1”，并在最后一段误写为“$m+1=8$”；这里按样例及 $m=8$ 修正为“样例输出 1”和“$m+1=9$”。

数据范围

对于所有数据：$2\le n\le5\times10^5$，$n-1\le m\le2\times10^6$，$1\le q\le5\times10^5$，$1\le u_i,v_i\le n$，$u_i\ne v_i$，$1\le u\le n$，$1\le k\le m$。保证在地震之前，所有城市可以互相到达。

本题采用捆绑测试，并且开启所有合理的子任务依赖。