#include "evolution2.h"
#include<bits/stdc++.h>
using namespace std;
using vi=vector<int>;
const int N=10005;
/*
mt19937 rng(time(0));
int rnd(int l,int r)
{return rng()%(r-l+1)+l;}
int p[N],fa[N],id[N],nn;
vi tu,tv;
void gen()
{
    nn=rnd(3,20);
    for(int i=1;i<nn;i++)fa[i]=0;
    for(int i=0;i<nn;i++)p[i]=i;
    for(int i=0;i<nn*2;i++)
    {
        int x=rnd(1,nn-1),y=rnd(1,nn-1);
        swap(p[x],p[y]);
    }tu.clear(),tv.clear();
    for(int i=1;i<nn;i++)
    tu.push_back(fa[i])
    ,tv.push_back(i);
}
bool compare(int x,int y)
{
    assert(0<=x&&x<nn);
    assert(0<=y&&y<nn);
    return p[x]<p[y];
}
*/
vi edge[N];bool vs[N];
int pos[N],m;
void ins(int x,int y)
{
    for(int i=m;i>=x;i--)
    pos[i+1]=pos[i];m++;pos[x]=y;
}using ld=long double;
vi vc[N];vi mg(vi x,vi y)
{
    if(!x.size())return y;
    if(!y.size())return x;
    if(x.size()>y.size())x.swap(y);
    int sx=x.size(),sy=y.size();ld sum=0;
    for(int i=1;i<=sx+sy;i++)sum+=log2(i);
    for(int i=1;i<=sy;i++)sum-=log2(i);
    for(int i=1;i<=sx;i++)sum-=log2(i);
    if(sx+sy-1<=ceil(sum)*1.4)
    {
        vi rs;int px=0,py=0;
        while(px<sx&&py<sy)
        if(compare(x[px],y[py]))
        rs.push_back(x[px]),px++;
        else rs.push_back(y[py]),py++;
        while(px<sx)rs.push_back(x[px]),px++;
        while(py<sy)rs.push_back(y[py]),py++;
        return rs;
    }else if(sx<=5&&sy<=5)
    {
        m=sy;int ls=1;
        for(int i=1;i<=m;i++)pos[i]=y[i-1];
        bool tg=0;for(int c:x)
        {
            int l=ls,r=m,mid;
            while(l<r)
            {
                mid=l+(r-l)*0.5;
                if(compare(pos[mid],c))l=mid+1;
                else r=mid;
            }if(r==m&&(tg||compare(pos[r],c)))
            {r++;tg=1;}ins(r,c);ls=r+1;
        }vi rs;
        for(int i=1;i<=m;i++)
        rs.push_back(pos[i]);
        return rs;
    }
    int lt=sy/sx,i=0;for(int t=0;t<sx;t++)
    {
        int c=x[t];while(i+lt<sy&&
        compare(y[i+lt],c))i+=lt;
		int l=0,r=min(sy-i,lt),mid;
		while(l<r)
		{
			mid=(l+r)/2;
			if(compare(y[i+mid],c))
            l=mid+1;else r=mid;
		}pos[t]=i+l,i+=l;
    }vi rs=y;for(int i=sx-1;i>=0;i--)
    rs.insert(rs.begin()+pos[i],x[i]);
    return rs;
}
int id[N],sz[N],k=0;
bool cmp(int x,int y)
{return sz[x]>sz[y];}
void dfs(int u,int f)
{
    vc[u].clear();sz[u]=1;
    for(int v:edge[u])
    {
        if(v==f)continue;
        dfs(v,u),sz[u]+=sz[v];
    }k=0;for(int v:edge[u])
    if(v^f)id[++k]=v;
    sort(id+1,id+k+1,cmp);
    for(int i=1;i<=k;i++)
    vc[u]=mg(vc[u],vc[id[i]]);
    vc[u].insert(vc[u].begin(),u);
}
int tmp[N],t[N],cnt=0;
void srt(int l,int r)
{
    if(l>=r)return;
    int mid=(l+r)>>1;
    srt(l,mid),srt(mid+1,r);
    int p1=l,p2=mid+1;cnt=0;
    while(p1<=mid&&p2<=r)
    if(compare(tmp[p1],tmp[p2]))
    t[++cnt]=tmp[p1],p1++;
    else t[++cnt]=tmp[p2],p2++;
    while(p1<=mid)
    t[++cnt]=tmp[p1],p1++;
    while(p2<=r)
    t[++cnt]=tmp[p2],p2++;
    for(int i=1;i<=cnt;i++)
        tmp[i+l-1]=t[i];
}
vi recover(int n,vi U,vi V)
{
    for(int i=0;i<n;i++)edge[i].clear();
    for(int i=0;i<n-1;i++)
    edge[U[i]].push_back(V[i]);
    int rt=0;for(int i=0;i<n;i++)vs[i]=0;
    for(int i=0;i<n-1;i++)vs[V[i]]=1;
    for(int i=0;i<n;i++)if(!vs[i])rt=i;
    bool flag=1;for(int i=0;i<n;i++)
    flag&=(U[i]==0);if(flag)
    {
        vi rs(n);rs[0]=0;
        for(int i=1;i<n;i++)tmp[i]=i;
        srt(1,n-1);
        for(int i=1;i<n;i++)
        rs[tmp[i]]=i;
        return rs;
    }dfs(rt,0);vi rs(n);
    for(int i=0;i<n;i++)
    rs[vc[rt][i]]=i;
    return rs;
}
/*
int main()
{
    for(int i=1;i<=10;i++)
    {
        gen();bool fl=1;
        vi rs=recover(nn,tu,tv);
        for(int i=0;i<nn;i++)
        fl&=(p[i]==rs[i]);
        for(int i=0;i<nn;i++)cout<<p[i]<<' ';cout<<'\n';
        for(int i=0;i<nn;i++)cout<<rs[i]<<' ';cout<<'\n';
        cout<<fl<<'\n';
    }
    return 0;
}
*/