1 #include <cstdio>  2 const int sizeOfPoint=500005;  3 const int sizeOfEdge=500005;  4   5 inline int lg(int);  6 inline int min(int, int);  7 inline int max(int, int);  8 inline void swap(int & , int & );  9 inline int getint(); 10 inline void putint(int); 11  12 struct edge {int point; edge * next;}; 13 edge memory[sizeOfEdge], * port=memory; 14 inline edge * newedge(int, edge * ); 15  16 struct node {int x, y; inline node(int=0, int=0);}; 17 inline bool operator < (node, node); 18  19 int n, m, k; 20 int p[sizeOfPoint]; 21 edge * e[sizeOfPoint]; 22 int a[32][sizeOfPoint]; 23 int g[sizeOfPoint], s[sizeOfPoint]; 24 int f[sizeOfPoint], d[sizeOfPoint]; 25 int l[sizeOfPoint]; 26 bool v[sizeOfPoint], b[sizeOfPoint]; 27 inline void bfs(int); 28 inline int lca(int, int); 29  30 int main() 31 { 32     n=getint(), k=getint(); 33     for (int i=1;i<=n;i++) 34     { 35         p[i]=getint(); 36         e[p[i]]=newedge(i, e[p[i]]); 37     } 38  39     for (int i=1;i<=n;i++) if (!v[i]) 40     { 41         int u=i; 42         for ( ;!b[u];u=p[u]) b[u]=true; 43  44         ++m; 45         for (int j=1;!l[u];j++, u=p[u]) 46         { 47             g[u]=m; 48             s[m]++; 49             l[u]=j; 50             bfs(u); 51         } 52     } 53  54     for (int i=1;i<=k;i++) 55     { 56         int a=getint(), b=getint(); 57  58         if (g[f[a]]!=g[f[b]]) 59         { 60             putint(-1), putchar(‘ ‘); 61             putint(-1), putchar(‘\n‘); 62         } 63         else if (f[a]==f[b]) 64         { 65             int c=lca(a, b); 66             putint(d[a]-d[c]), putchar(‘ ‘); 67             putint(d[b]-d[c]), putchar(‘\n‘); 68         } 69         else 70         { 71             int o=s[g[f[a]]]; 72             node ans1=node(d[a], d[b]), ans2=node(d[a], d[b]); 73  74             if (l[f[a]]<l[f[b]]) 75             { 76                 ans1.x+=l[f[b]]-l[f[a]]; 77                 ans2.y+=o-(l[f[b]]-l[f[a]]); 78             } 79             else 80             { 81                 ans1.x+=o-(l[f[a]]-l[f[b]]); 82                 ans2.y+=l[f[a]]-l[f[b]]; 83             } 84  85             if (ans1<ans2) 86             { 87                 putint(ans1.x), putchar(‘ ‘); 88                 putint(ans1.y), putchar(‘\n‘); 89             } 90             else 91             { 92                 putint(ans2.x), putchar(‘ ‘); 93                 putint(ans2.y), putchar(‘\n‘); 94             } 95         } 96     } 97  98     return 0; 99 }100 101 inline int lg(int x)102 {103     return 31-__builtin_clz(x);104 }105 inline int min(int x, int y)106 {107     return x<y?x:y;108 }109 inline int max(int x, int y)110 {111     return x>y?x:y;112 }113 inline void swap(int & x, int & y)114 {115     int t=x; x=y; y=t;116 }117 inline int getint()118 {119     register int num=0;120     register char ch;121     do ch=getchar(); while (ch<‘0‘ || ch>‘9‘);122     do num=num*10+ch-‘0‘, ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘);123     return num;124 }125 inline void putint(int num)126 {127     char stack[11];128     register int top=0;129     if (num==0) stack[top=1]=‘0‘;130     if (num<0) putchar(‘-‘), num=-num;131     for ( ;num;num/=10) stack[++top]=num%10+‘0‘;132     for ( ;top;top--) putchar(stack[top]);133 }134 135 inline edge * newedge(int point, edge * next)136 {137     edge * ret=port++;138     ret->point=point; ret->next=next;139     return ret;140 }141 142 inline node::node(int _x, int _y)143 {144     x=_x;145     y=_y;146 }147 inline bool operator < (node a, node b)148 {149     if (max(a.x, a.y)<max(b.x, b.y)) return true;150     if (max(a.x, a.y)>max(b.x, b.y)) return false;151     if (min(a.x, a.y)<min(b.x, b.y)) return true;152     if (min(a.x, a.y)>min(b.x, b.y)) return false;153     return a.y<b.y;154 }155 156 inline void bfs(int root)157 {158     static int q[sizeOfPoint];159     int s=0, t=0;160     d[root]=0;161     f[root]=root;162 163     for (q[t++]=root;s<t;s++)164     {165         int u=q[s];166         v[u]=true;167         if (d[u]>1)168         {169             int lim=lg(d[u]);170             for (int i=1;i<=lim;i++)171                 a[i][u]=a[i-1][a[i-1][u]];172         }173 174         for (edge * i=e[u];i;i=i->next) if (i->point!=p[u] && !l[i->point])175         {176             d[i->point]=d[u]+1;177             f[i->point]=root;178             a[0][i->point]=u;179             q[t++]=i->point;180         }181     }182 }183 inline int lca(int u, int v)184 {185     int dist;186     if (d[u]<d[v]) swap(u, v);187     while ((dist=d[u]-d[v])) u=a[__builtin_ctz(dist)][u];188     if (u==v) return u;189     for (int i=31;i>=0;i--)190         if (a[i][u]!=a[i][v])191             u=a[i][u],192             v=a[i][v];193     return a[0][u];194 }