Migrated from Lutece 2989 a DAG problem

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

你知道DAG吗？

没错，就是Daily Appreciate Genshin。（精神错乱）

DAG是指Directed Acylic Graph，有向无环图。即图中所有边均为有向边，且不存在一点，满足从该点出发，经过若干条（至少一条）有向边后回到该点。

这个问题就是一个关于DAG的问题：

给定一个 $n$ 个点、$m$ 条边的有向无环图，点编号从 $1$ 到 $n$，每条边上有一个字符，任意两条边上的字符不相同（即有严格的字典序大小关系）。显然，如果把某路径经过的边上的字符按顺序连起来，则任何一条路径都对应了一个字符串。

现在有 $q$ 个询问，每个询问给定一个起点 $u$ 和参数 $k$ ，表示：把从$u$出发的所有至少经过了一条边的路径对应的字符串拿来按字典序排序，求字典序第 $k$ 小的字符串对应的路径的终点的编号。

由于某种神秘力量的影响，我们无法得知每条边上的字符具体是什么。不过为了保证路径排序结果的唯一性，输入中会按边上字符的字典序从小到大给出每一条边。

Input

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

接下来 $m$ 行，每行包含两个整数 $u,v$，表示有一条从 $u$ 到 $v$ 的有向边。边按照边上字符的字典序从小到大依次给出。

接下来 $q$ 行，每行包含两个整数 $u,k$，描述了一次询问。

Output

输出包含 $q$ 行。对于每一个询问，输出一行一个整数，表示所求路径的终点编号，如果不存在这样一条路径，则本行输出-1。

Samples

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

2
4
3
4
5
4
-1
-1

Constraints

$1\le n,m,q \le 2*10^5,1\le u,v\le n,1\le k\le 10^9$

Note

$A$ 和 $B$ 两个字符串的字典序大小比较：

1. 对于 $A$ 和 $B$ 两个串，其字典序大小关系取决于两个串中第一个不同的位置的字符的字典序大小关系。

2. 特别地，如果 $A$ 是 $B$ 的前缀，则 $A$ 的字典序小于 $B$的字典序。

例如：

1. 字符串abbd的字典序小于字符串abca的字典序。

2. 字符串abcd的字典序小于字符串abcdaaa的字典序。

题目背景：（大雾）

Resources

2023 UESTC ICPC Training for Search and Dynamic Programming