显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=600000+50;
struct wer{
int to,next;
}eg[2*N];
int head[N]={0},ne=1,t[N];
void add(int x,int y){
eg[++ne]={y,head[x]};
head[x]=ne;return ;
}
int n,q,lgn;
int vis[N]={0};
bool in[N],huan[N];
int st[N],tp=0,cnt=0,tot=0;
vector<int>v[N],fr[N];
int d[N],c[N],anc[N][30];
int rt[N],hid[N],hpos[N],dir[N];
void dfs(int pt,int lst){
st[++tp]=pt;vis[pt]=1;
for (int i=head[pt];i!=0;i=eg[i].next){
int x=eg[i].to;
if (i==(lst^1)||vis[x]==2)continue;
if (vis[x]==1){
cnt++;
while(st[tp]!=x){
v[cnt].push_back(st[tp]);
vis[st[tp]]=2;huan[st[tp]]=1;tp--;
}
v[cnt].push_back(x);huan[x]=1;vis[x]=2;tp--;
return ;
}
if (vis[x]==0) dfs(x,i);
}
vis[pt]=2;tp--;
return ;
}
int dep[N];
void dfs2(int pt,int id,int id2){
c[pt]=id;d[pt]=id2;
for (int i=0;i<fr[pt].size();i++){
int x=fr[pt][i];
if (huan[x])continue;
dep[x]=dep[pt]+1;anc[x][0]=pt;
dfs2(x,id,id2);
}
return ;
}
int lca(int a,int b){
if (dep[a]<dep[b])swap(a,b);
for (int i=lgn;i>=0;i--){
if (anc[a][i]!=0&&dep[anc[a][i]]>=dep[b])a=anc[a][i];
if (a==b)return a;
}
for (int i=lgn;i>=0;i--){
if (anc[a][i]!=anc[b][i]){
a=anc[a][i];b=anc[b][i];
}
}
return anc[a][0];
}
struct sdf{
int x,y;
}ans[4];
bool cmp(sdf a,sdf 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>=a.y;
}
inline int read(){
int tmp=0;char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))tmp=(tmp<<3)+(tmp<<1)+(ch^48),ch=getchar();
return tmp;
}
inline void write(int x){
if (x>9)write(x/10);
putchar(x%10+'0');
}
int main(){
freopen ("rdz.in","r",stdin);
freopen ("rdz.out","w",stdout);
scanf("%d%d",&n,&q);
lgn=1.0*log(n)/log(2);
for (int i=1;i<=n;i++){
int x=read();
in[x]=1;fr[x].push_back(i);
add(i,x);add(x,i);t[i]=x;
}
for (int i=1;i<=n;i++){
if (!vis[i])dfs(i,0);
}
for (int i=1;i<=cnt;i++){
for (int j=0;j<v[i].size();j++){
int x=v[i][j];
dep[x]=0;dfs2(x,++tot,i);
hpos[x]=j+1;hid[x]=i;rt[tot]=x;
}
if (v[i].size()==1)continue;
if (t[v[i][1]]==v[i][2])dir[i]=1;
else dir[i]=2;
}
for (int i=1;i<=lgn;i++){
for (int j=1;j<=n;j++)anc[j][i]=anc[anc[j][i-1]][i-1];
}
while(q--){
int a=read(),b=read();
if (d[a]!=d[b]){
printf("-1 -1\n");continue;
}
if (c[a]==c[b]){
int l=lca(a,b);
write(dep[a]-dep[l]);putchar(' ');
write(dep[b]-dep[l]);putchar('\n');
}
else{
int x=hpos[rt[c[a]]],y=hpos[rt[c[b]]];
int sz=v[hid[rt[c[a]]]].size();
int lena=(y-x+sz)%sz,lenb=(x-y+sz)%sz;
if (dir[hid[rt[c[a]]]]==2)swap(lena,lenb);
ans[1]={lena+dep[a],dep[b]},ans[2]={dep[a],lenb+dep[b]};
sort(ans+1,ans+3,cmp);
write(ans[1].x);putchar(' ');
write(ans[1].y);putchar('\n');
}
}
return 0;
}
op_组撒头屯