尖塔第四强的高手
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

机宝是《杀戮尖塔》中第四强的高手，他掌握着大量随机数，擅长跳跃世界线。今天他遇到了一个精英怪，在一番苦战后他决定跳跃世界线，但由于他的集中掉完了，因此需要你帮助他跳跃世界线。
世界线可以表示为一棵 n 个结点的有根树，结点编号从 1 到 n，对于其中任意一棵子树，该子树的根节点可以到达该子树内任意一点（包括子树根节点自己）。
设数列 F_1=1,F_2=2,F_i=F_{i-1}+F_{i-2}(i\ge 3)。机宝有 q 次询问，每次询问他会给出两个正整数 x,k，生成点集 \{x+F_i\mid i\in\mathbb{N},i\ge k,x+F_i\le n\}，机宝想找一个结点，使得该结点能到达点集中任意一点，并且在所有符合要求的结点中，该结点距离根节点最远。

输入描述:

第一行包含三个正整数 n,r,q，分别表示树的结点数量、根节点编号和询问次数。 
接下来 n-1 行每行包含两个正整数 u,v，表示编号为 u 的结点和编号为 v 的结点之间有一条边（数据保证可以构成树）。 
接下来 q 行每行包含两个正整数 x,k，含义同题目描述。 
1\le n,q\le 10^5，1\le r,u,v,x\le n，1\le k\le 10^9。

输出描述:

输出共 q 行，每行一个整数，表示符合题目要求的结点编号。如果不存在符合题目要求的结点，输出 0。
示例1

输入

复制 
6 1 3
1 2
1 3
2 4
2 5
4 6
4 1
1 4
6 1

输出

复制 
2
6
0

说明

第一次询问的点集为 \{5,6\}，结点 1 和结点 2 都能到达点集中任意一点，结点 2 距离根节点最远，答案是 2。 
第二次询问的点集为 \{6\}，答案是 6。 
第三次询问为空集，答案是 0。
示例2

输入

复制 
10 7 4
1 2
1 3
2 6
3 4
4 5
4 7
5 9
6 10
7 8
2 5
4 3
7 3
7 2

输出

复制 
10
7
10
4