[POI] 19th stage I - pD Rendezvous

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#define N 500005
using namespace std;
struct P{
    int x,y;
};
int next[N],dp[N][25],team[N],visit[N]={0},dfs[N]={0},circle[N],circle_n[N],root[N],tadd=0;
int n,m,p,q;
vector<int> pre[N],s[N];
vector<P> arr;
int cmp(P a,P b){
    if(max(a.x,a.y)!=max(b.x,b.y)) return max(a.x,a.y)<max(b.x,b.y);
    if(min(a.x,a.y)!=min(b.x,b.y)) return min(a.x,a.y)<min(b.x,b.y);
    return a.x>b.x;
}
void dfs_team(int k,int f){
    int i,r;
    team[k]=tadd;
    for(i=0;i<s[k].size();i++){
        r=s[k][i];
        if(r==f) continue;
        if(visit[r]==0){
            visit[r]=1;
            dfs_team(r,k);
        }
        else p=k;
    }
}
void dfs_level(int k,int add,int rt){
    int i;
    dfs[k]=add;
    root[k]=rt;
    for(i=0;i<pre[k].size();i++)
        dfs_level(pre[k][i],add+1,rt);
}
void dfs_circle(int k,int f,int add){
    int i,r;
    if(add+1>q) q=add+1;
    circle[k]=add;
    dp[k][0]=-1;
    if(next[k]!=p)
    dfs_circle(next[k],k,add+1);
    for(i=0;i<pre[k].size();i++){
        r=pre[k][i];
        if(r!=f && circle[r]==-1) dfs_level(r,1,k);
    }
    circle_n[k]=q;
}
P two_circle(int a,int b,int pa,int pb,int t){
    int X,Y;
    X=(b+t-a)%t,Y=(a+t-b)%t;
    arr.clear();
    arr.push_back((P){pa,Y+pb});
    arr.push_back((P){X+pa,pb});
    sort(arr.begin(),arr.end(),cmp);
    return arr[0];
}
int LCA(int x,int y){
    int i,d;
    if(dfs[x]>dfs[y]) swap(x,y);
    d=dfs[y]-dfs[x];
    for(i=0;i<=20;i++)
        if(d&(1<<i))
            y=dp[y][i];
    if(x==y) return x;
    for(i=20;i>=0;i--){
        if(dp[x][i]==-1) continue;
        if(dp[x][i]!=dp[y][i]){
            x=dp[x][i];
            y=dp[y][i];
        }
    }
    return dp[x][0];
}
int main(){
    int i,j,x,y,a,b;
    memset(dp,-1,sizeof(dp));
    memset(circle,-1,sizeof(circle));
    memset(circle_n,-1,sizeof(circle_n));
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&next[i]);
        dp[i][0]=next[i];
        pre[next[i]].push_back(i);
        s[next[i]].push_back(i);
        s[i].push_back(next[i]);
        root[i]=i;
    }
    for(i=1;i<=n;i++){
        if(visit[i]==0){
            dfs_team(i,0),tadd++;
            q=0;
            dfs_circle(p,0,0);
        }
    }
    for(i=1;i<=20;i++)
        for(j=1;j<=n;j++)
            dp[j][i]=dp[dp[j][i-1]][i-1];
    for(i=0;i<m;i++){
        scanf("%d%d",&x,&y);
        if(team[x]!=team[y]) puts("-1 -1");
        else if(circle[x]!=-1 && circle[y]!=-1){
            P ans=two_circle(circle[x],circle[y],0,0,circle_n[x]);
            printf("%d %d\n",ans.x,ans.y);
        }
        else if(root[x]!=root[y]){
            P ans=two_circle(circle[root[x]],circle[root[y]],dfs[x],dfs[y],circle_n[root[x]]);
            printf("%d %d\n",ans.x,ans.y);
        }
        else if(circle[x]!=-1) printf("0 %d\n",dfs[y]);
        else if(circle[y]!=-1) printf("%d 0\n",dfs[x]);
        else{
            p=LCA(x,y);
            printf("%d %d\n",dfs[x]-dfs[p],dfs[y]-dfs[p]);
        }
    }
}