该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

EX 环跳查询

题目描述

给定一张包含 $n$ 个节点、$m$ 条边的无向简单图，节点编号为 $1 \sim n$。图不一定连通。

现有一个棋子，初始时放置在图中的某个节点上。你可以对该棋子进行若干次移动操作。每次操作的规则如下：

假设当前棋子位于节点 $x$，你可以选择图中任意一个经过节点 $x$ 的简单环，并将棋子直接移动到该环上的任意一个节点 $y$（允许原地不动，即 $y=x$）。

注意：

• 简单环定义为：长度至少为 $3$，且除了起点和终点重合外，其余节点均不重复的路径；
• 图的结构在操作过程中不会发生改变；
• 同一个环可以被重复多次使用；
• 如果当前所在节点不在任何简单环上，则该步无法进行任何移动。

现给出 $q$ 次独立询问。每次询问给定两个整数 $u$ 和 $k$，表示棋子初始位于节点 $u$，你至多可以进行 $k$ 次移动操作。你需要求出：最终棋子可能停留在多少个不同的节点上？

形式化地，定义节点集合 $S(u,k)$ 为：

对于每组询问，你需要输出 $|S(u,k)|$ 的值。

输入格式

第一行包含三个整数 $n, m, q$，分别表示图的节点数、边数和询问次数。

接下来 $m$ 行，每行包含两个整数 $a, b$，表示节点 $a$ 和节点 $b$ 之间存在一条无向边。保证输入的图为简单图（即无重边和自环）。

接下来 $q$ 行，每行包含两个整数 $u, k$，表示一组询问，参数意义如题目描述所述。

数据范围

• $1 \le n, q \le 2 \times 10^5$
• $0 \le m \le 2 \times 10^5$
• $1 \le a, b \le n$ 且 $a \ne b$
• $1 \le u \le n$
• $0 \le k \le 2 \times 10^5$

输出格式

输出共 $q$ 行。对于每组询问，输出一行一个整数，表示该次询问对应的答案 $|S(u,k)|$。

输入输出样例 #1

输入 #1

6 7 5
1 2
2 3
3 1
3 4
4 5
5 3
5 6
1 0
1 1
1 2
6 10
3 1

输出 #1

1
3
5
1
5

输入输出样例 #2

输入 #2

5 4 4
1 2
2 3
3 4
4 5
1 0
1 1
3 100
5 2

输出 #2

1
1
1
1

说明/提示

样例 1：

图中有两个三角形 $(1,2,3)$ 与 $(3,4,5)$，它们在顶点 3 处相交，另外有一条桥边 $(5,6)$。

• 询问 $(1,0)$：不能进行操作，只能停在 1。
• 询问 $(1,1)$：可以在三角形 $(1,2,3)$ 中任意跳转，因此可达 ${1,2,3}$。
• 询问 $(1,2)$：先跳到 3，再利用三角形 $(3,4,5)$，可达 ${1,2,3,4,5}$。
• 询问 $(6,10)$：顶点 6 不在任何简单环上，无法进行任何操作，因此答案为 1。
• 询问 $(3,1)$：顶点 3 同时在两个三角形上，一步内可到达 ${1,2,3,4,5}$。

样例 2：

整张图是一棵树，不存在任何简单环，因此任意点都无法进行操作。