1 #include
     
       2 #include
      
        3 using namespace std; 4 int m, n, root; 5 struct qwq{ 6     int t, nex; 7 }edge[2*500001]; 8 int d[500001], f[500001][25], head[500001];//d数组记录深度  9 int cnt;10 void add(int x, int y){
   //链式前向星存图 11     edge[++cnt].t=y; 12     edge[cnt].nex=head[x];13     head[x]=cnt;14 }15 void dfs(int a, int ft){
   //预处理 16     d[a]=d[ft]+1;17     for(int i=0; i<=20; i++) 18         f[a][i+1]=f[f[a][i]][i];19     for(int i=head[a]; i; i=edge[i].nex){20         int v=edge[i].t;21         if(v==ft) continue;22         f[v][0]=a;23         dfs(v, a);24     }25 }26 int lca(int x,int y){27     if(d[x]
       
        =0; i--){29         if(d[f[x][i]]>=d[y]) x=f[x][i];30         if(x==y)    return x;31     }32     for(int i=21; i>=0; i--)33         if(f[x][i]!=f[y][i]) x=f[x][i], y=f[y][i];34     return f[x][0];35 }36 int main(){37     scanf("%d%d%d",&n,&m,&root);38     for(int i=1; i