萌新刚学OI

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int N=55,M=105;
ll mod1=1000000613,mod2=1000000433;
ll read(){
	ll f=1,w=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while('0'<=ch&&ch<='9'){
		w=w*10+ch-'0';
		ch=getchar();
	}
	return w;
}
int n,m;
int tot,to[M],nxt[M],head[N];
int siz[N],min1;
vector<int>min2;
string tmp,f[N],g[N],mn[N];
void add(int u,int v){
	to[tot]=v;
	nxt[tot]=head[u];
	head[u]=tot++;
}
void dfs1(int u,int fa){
	int maxx=0;
	siz[u]=1;
	for(int i=head[u];~i;i=nxt[i]){
		int v=to[i];
		if(v==fa)	
			continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		maxx=max(maxx,siz[v]);
	}
	maxx=max(maxx,n-maxx);
	if(min1>maxx){
		min1=maxx;
		vector<int>t;
		swap(min2,t);
		min2.push_back(u);
	}else if(min1==maxx){
		min2.push_back(u);
	}
}
void dfs2(int u,int fa){
	f[u]="0";
	for(int i=head[u];~i;i=nxt[i]){
		int v=to[i];
		if(v==fa)
			continue;
		dfs2(v,u);
	}
	int tot=0;
	for(int i=head[u];~i;i=nxt[i]){
		int v=to[i];
		if(v==fa)
			continue;
		g[++tot]=f[v];
	}
	sort(g+1,g+1+tot);
	for(int i=1;i<=tot;i++)
		f[u]+=g[i];
	f[u]+="1";
}
int main(){
	m=read();
	for(int j=1;j<=m;j++){
		tmp="1";
		n=read();
		tot=0;
		min1=n+1;
		memset(head,-1,sizeof head);
		for(int u=1;u<=n;u++){
			int v=read();
			if(v){
				add(u,v);
				add(v,u);
			}
		}
		dfs1(1,0);
		for(int i=0;i<min2.size();i++){
			dfs2(min2[i],0);
			tmp=min(tmp,f[min2[i]]);
		}
		mn[j]=tmp;
		bool flag=0;
		for(int i=1;i<j;i++){
			if(mn[i]==mn[j]){
				printf("%d\n",i);
				flag=1;
				break;
			}
		}
		if(!flag)
			printf("%d\n",j);
	}
	return 0;
}