水紫一道：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
#define PII pair<int,int>
vector<int>G[N],G2[N];vector<PII>G3[N]; 
int tsp,cnt,scc[N],low[N],dfn[N];
stack<int>stk;
void tarjan(int x)
{
    low[x]=dfn[x]=++tsp;
    stk.push(x);
    for(int y:G[x])
    {
        if(dfn[y]==0)
        {
            tarjan(y);
			low[x]=min(low[x],low[y]);
			if(low[y]==dfn[x])
    		{
        		cnt++;G2[x].push_back(cnt);G2[cnt].push_back(x);
        		for(int z=-1;z!=y;)
        		{
           			z=stk.top();stk.pop();
           			G2[cnt].push_back(z);
           			G2[z].push_back(cnt);
           			scc[z]=cnt;
        		}
   			}
        }
        else low[x]=min(low[x],dfn[y]);
    }   
}
int D,dep[N],st[N][20];int n,m;
void dfs(int x,int f)
{
    dep[x]=dep[f]+1;
    st[x][0]=f;for(int i=1;i<=D;i++)st[x][i]=st[st[x][i-1]][i-1];
    for(int y:G2[x])if(y!=f)dfs(y,x);
}
int lca(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y); 
    for(int i=D;i>=0;i--)if(dep[st[x][i]]>=dep[y])x=st[x][i];
    if(x==y)return x;
	for(int i=D;i>=0;i--)if(st[x][i]!=st[y][i])x=st[x][i],y=st[y][i];
    return st[x][0];
}
int a[N],d[N],v[N];
void dij(int st)
{
	priority_queue<PII,vector<PII>,greater<PII>>q;
	memset(d,0x3f,sizeof(d));d[st]=0;
	q.push({0,st});
	while(!q.empty())
	{
		int x=q.top().second;q.pop();
		if(v[x])continue;v[x]=1;
		for(auto i:G3[x])
		{
			int y=i.first,w=i.second;
			if(d[y]>d[x]+w)
				d[y]=d[x]+w,q.push({d[y],y});
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++)
	{
		int x,y;cin>>x>>y;
		G[x].push_back(y);
		G3[x].push_back({y,1});
		G[y].push_back(x);
		G3[y].push_back({x,1});
	}
	cnt=n;for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i),stk.pop();
	D=log2(cnt);dfs(1,0);
	bool bk=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]==i){bk=1;G3[0].push_back({i,0});G3[i].push_back({0,0});continue;}
		for(int j:G[i])
		{
			int x=a[i],y=a[j],t=lca(x,y);
			if((lca(j,x)==j||lca(j,y)==j)&&lca(j,t)==t)
			{
				G3[0].push_back({i,1});
				G3[i].push_back({0,1});
				bk=1;break;
			}	
		}
	}
	if(!bk)
	{
		for(int i=1;i<=n;i++)cout<<-1<<' ';
		return 0;
	}
	dij(0);
	for(int i=1;i<=n;i++)cout<<d[i]<<' ';
	return 0;
}

P9760 [COCI 2022/2023 #3] Skrivača

首先注意到 Marin 必然要走到割点 $v$ 上，且上一步中 Luka 从 $a_u$ 走到 $a_v$，其中 $a_u$ 与 $a_v$ 被划分成两部分，可以用圆方树直接维护，维护出所有与割点相邻的 $a_u,a_v$ 被划分的点对。

另外，当存在 $a_k=k$ 时，也要考虑一下该情况。走到这个点对就行。

然后 bfs 一下就做完了。

::::info[Code]

#include <queue>
#include <vector>
#include <iostream>

using namespace std;

const int N = 4e5 + 10; 

int n, m, cnt, a[N], ans[N]; 
vector <int> g[N], ng[N]; 
int dfn[N], low[N], tim, st[N], tp;
vector < pair<int, int> > edge; 

void tarjan (int u) {
    dfn[u] = low[u] = ++ tim;
    st[++ tp] = u;
    for (const auto& v : g[u]) 
        if (!dfn[v]) {
            tarjan (v);
            low[u] = min (low[u], low[v]);
            if (low[v] >= dfn[u]) { 
                ++ cnt;
                int curr;
                do {
                    curr = st[tp --];
                    ng[cnt].push_back (curr);
                    ng[curr].push_back (cnt);
                } while (curr != v);
                ng[cnt].push_back (u);
                ng[u].push_back (cnt);
            }
        } else low[u] = min (low[u], dfn[v]);
}

int pa[N][20], dep[N];

void dfs (int u, int p) {
    pa[u][0] = p;
    for (int i = 1; i <= 18; i ++) pa[u][i] = pa[pa[u][i - 1]][i - 1];
    dep[u] = dep[p] + 1;
    for (auto v : ng[u]) {
        if (v == p) continue;
        dfs (v, u);
    }
}

int lca (int u, int v) {
    if (dep[u] < dep[v]) swap (u, v);
    for (int i = 18; ~i; i --)
        if (dep[pa[u][i]] >= dep[v]) u = pa[u][i];
    if (u == v) return u;
    for (int i = 18; ~i; i --)
        if (pa[u][i] != pa[v][i]) u = pa[u][i], v = pa[v][i];
    return pa[u][0];
}

int getdis (int u, int v) {
    return dep[u] + dep[v] - 2 * dep[ lca (u, v) ];
}

int main (void) {

    scanf ("%d%d", &n, &m);
    cnt = n;
    for (int i = 1; i <= 2 * n; i ++) ans[i] = -1;
    for (int i = 1; i <= n; i ++) scanf ("%d", a + i);
    for (int i = 1, u, v; i <= m; i ++) scanf ("%d%d", &u, &v), g[u].push_back (v), g[v].push_back (u), edge.emplace_back (u, v), edge.emplace_back (v, u);
    tarjan (1), dfs (1, 0); 

    queue <int> q;
    for (int i = 1; i <= n; i ++) if (a[i] == i) ans[i] = 0, q.push(i);
    for (auto& [u, v] : edge) {
        if (ans[u] == 0) continue; 
        int st = a[u], ed = a[v];
        if (getdis (st, ed) == getdis (st, v) + getdis (v, ed) && ans[u] == -1) ans[u] = 1, q.push(u);
    }
    while (!q.empty ()) {
        int u = q.front ();
        q.pop ();
        for (int v : g[u]) if (ans[v] == -1) ans[v] = ans[u] + 1, q.push(v);
    }

    for (int i = 1; i <= n; i ++) printf ("%d ", ans[i]);
    puts ("");

    return 0;
}

::::