给定一棵有n个点的无根树，相邻的点之间的距离为1，一开始你位于m点。之后你将依次收到k个指令，每个指令包含两个整数d和t，你需要沿着最短路在t步之内（包含t步）走到d点，如果不能走到，则停在最后到达的那个点。请在每个指令之后输出你所在的位置。

第一行包含三个正整数n,m,k(1<=m<=n<=1000000,1<=k<=1000000)。

接下来n-1行，每行包含两个正整数x,y(1<=x,y<=n)，描述一条树边。

接下来k行，每行两个整数d,t(1<=d<=n,0<=t<=10^9)，描述一条指令。

输出一行，包含k个正整数，即执行每条指令后你所在的位置。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

using namespace std;

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define maxn 1000010

struct EdgeNode{int to,next;}edge[maxn<<];

int head[maxn],cnt=;

void add(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}

void insert(int u,int v) {add(u,v); add(v,u);}

int n,m,k;

int deep[maxn],father[maxn][];

void DFS(int now,int last)

{

    for (int i=; i<=; i++)

        if (deep[now]>=(<<i)) father[now][i]=father[father[now][i-]][i-];

            else break;

    for (int i=head[now]; i; i=edge[i].next)

        if (edge[i].to!=last)

            {

                father[edge[i].to][]=now;

                deep[edge[i].to]=deep[now]+;

                DFS(edge[i].to,now);

            }

}

int LCA(int x,int y)

{

    if (deep[x]<deep[y]) swap(x,y);

    int dd=deep[x]-deep[y];

    for (int i=; (<<i)<=dd; i++)

        if ((<<i)&dd) x=father[x][i];

    for (int i=; i>=; i--)

        if (father[x][i]!=father[y][i])

            x=father[x][i],y=father[y][i];

    if (x==y) return x; return father[x][];

}

int main()

{

    n=read(),m=read(),k=read();

    for (int u,v,i=; i<=n-; i++) u=read(),v=read(),insert(u,v);

    DFS(,);

    for (int d,t,i=; i<=k; i++)

        {

            d=read(),t=read();

            int lca=LCA(m,d),dm=deep[m]-deep[lca],dd=deep[d]-deep[lca],D=dm+dd;

        //    printf("%d   ",D);

            if (D<=t)

                printf("%d ",m=d);

            else

                {

                    if (dm==t) m=lca;

                        else if (dm>t)

                            for (int j=; (<<j)<=t; j++)

                                if ((<<j)&t) m=father[m][j]; else;

                            else

                                {

                                    for (int j=; (<<j)<=(dd-(t-dm)); j++)

                                        if ((<<j)&(dd-(t-dm))) d=father[d][j]; else;

                                    m=d;

                                }

                    printf("%d ",m);

                }

        }

    return ;

}