题目背景

成本越低，赚的越多！

题目描述

T 国由 $n$ 座城市组成，首都在 $1$ 号城市，有 $(n-1)$ 条道路连接着这些城，且所有城市都可以通过这些道路到达首都。

有 $q$ 轮旅行活动，第 $i$ 次旅游会有一个参数 $(l_i,r_i)$，每次都有 $k$ 个人，他们每个人都会在编号在 $[l_i,r_i]$ 的城市中选择一个城市作为出发点。为了让每个人都有独处空间，任意两人不会选择同一个城市。

然后他们开始进行旅行。由于靠近首都的城市更高级，所以旅行者会向首都方向移动。

最终他们会在一个城市会聚，然后旅行结束。旅游公司没有足够经费让旅行者去更高级的城市，所以旅游公司会让他们会聚的城市离首都尽可能远。

现在旅游公司问你，他们会聚的地方，离首都距离最远是多少？两个城市之间的距离定义为最短路径上城市的个数（包括路径端点的两个城市）。

输入格式

第一行三个数 $n,q,k$。

接下来 $(n-1)$ 行，每行两个正整数 $u,v$ 表示一条边。

接下来 $q$ 行，每行两个正整数 $l,r$ 表示一次询问。

输出格式

共 $q$ 行，第 $i$ 行表示第 $i$ 次询问的答案。

5 7 2
1 2
1 3
2 4
2 5
1 3
1 4
1 5
2 4
2 5
3 5
4 5

1
2
2
2
2
2
2

提示

本题有捆绑测试，每个子任务均为 $20$ 分。

特殊性质：树的形态是以 $1$ 结点为链顶的一条链

对于 $100\%$ 的数据，$n\le 10^5,q\le10^5,1< k\le n,r-l+1\ge k$。