[USACO08DEC]Trick or Treat on the Farm G

#include <bits/stdc++.h>
using namespace std;
bool flag;
int n;
int nxt[112345];
int dis[112345]; //答案
int tot;
int dfn[112345];
int qst, qlen; //当前环起点、环长度
void dfs(int now, int st)
{
    int fa = nxt[now];
    //走到了走过的点
    if (dfn[fa] != 0)
    {
        //当前链找到了环
        if (dfn[fa] >= st)
        {
            qst = dfn[fa];
            qlen = dfn[now] - dfn[fa] + 1;
            dis[now] = qlen;
        }
        else
            dis[now] = dis[fa] + 1;
        return;
    }
    else
    {
        dfn[fa] = ++tot;
        dfs(fa, st);
        if (qst != -1 && dfn[now] >= qst)
            dis[now] = qlen;
        else
            dis[now] = dis[fa] + 1;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> nxt[i];
    for (int i = 1; i <= n; i++)
        if (dis[i] == 0)
        {
            dfn[i] = ++tot;
            qst = -1;
            dfs(i, tot);
        }
    for (int i = 1; i <= n; i++)
        cout << dis[i] << "\n";
    return 0;
}