#include "evolution.h"
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
// #define int ll
#define N 500005
using namespace std;
namespace 
{
    int n;
    multiset<int>S[N],all;
    int dis[N],ans[N];
    int ffa[N];
}
inline int mx(multiset<int>&s)
{
    if (s.empty()) return 0;
    return (*--s.end());
}
inline int smx(multiset<int>&s)
{
    if (s.size()<=1) return 0;
    return (*(--(--s.end())))+1;
}
inline int ssmx(multiset<int>&s)
{
    if (s.size()<=2) return 0;
    return (*(--(--(--s.end()))))+1;
}
inline int qry(int k)
{
    return max(mx(S[k]),smx(S[k]));
}
inline int qry1(int k)
{
    return max({mx(S[k])+smx(S[k]),smx(S[k])+ssmx(S[k])});
}
void init()
{
    n=1;
    all.insert(qry1(1));
}
void work(int k,int x)
{
    if (k==1) return;
    int fa=ffa[k];
    // cout<<k<<" "<<x<<" "<<ans[k]<<" "<<dis[k]<<" "<<qry1(k)<<" "<<S[k].size()<<endl;
    S[fa].insert(dis[k]);
    bool bl=1;
    all.erase(all.find(ans[fa]));

    bl&=(ans[fa]==max(x,qry1(fa)));
    bl&=(dis[fa]==qry(fa));
    // cout<<k<<" "<<x<<" "<<fa<<endl;

    ans[fa]=max(x,qry1(fa));
    all.insert(ans[fa]);
    // cout<<k<<" "<<x<<" "<<fa<<endl;
    // 
    if (bl) return;
    if (fa!=1) S[ffa[fa]].erase(S[ffa[fa]].find(dis[fa]));
    // cout<<k<<" "<<x<<" "<<fa<<endl;
    dis[fa]=qry(fa);
    work(fa,max(x,ans[fa]));
}

void observation(int P)
{
    ++n;
    ffa[n]=P;
    all.insert(qry1(n));
    work(n,0);
    // cout<<P<<" "<<n<<endl;
    // cout<<endl;
    // for (int i=1;i<=n;i++) cout<<ans[i]<<' ';
    // cout<<endl;
    // for (int i=1;i<=n;i++) cout<<dis[i]<<' ';
    // cout<<endl;
    // for (int i=1;i<=n;i++) cout<<mx(S[i])<<' ';
    // cout<<endl;
    // for (int i=1;i<=n;i++) cout<<smx(S[i])<<' ';
    // cout<<endl;
}
int analyze(int R)
{
    // cout<<"qry "<<R<<endl;
    return ans[R];
}