记录编号	123927	评测结果	AAAAAAAAAAA
题目名称	[POI 2001] 跳舞蝇的教练	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.155 s
提交时间	2014-10-01 15:47:54	内存使用	77.48 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const int SIZEN=2010,SIZEL=4010;
class T_note{//树的括号序列
public:
	int len;
	char *s;
	void print(void){cout<<s<<endl;}
};
int cmp(T_note a,T_note b){
	if(a.len<b.len) return -1;
	if(a.len>b.len) return 1;
	return strcmp(a.s,b.s);
}
bool operator < (T_note a,T_note b){
	return cmp(a,b)<0;
}
class R_note{//环的表示
public:
	int n;//环上点数
	T_note *Tlis;//环上诸点外向树的括号表示
	void print(void){
		cout<<n<<" trees as follows:\n";for(int i=1;i<=n;i++){cout<<i<<": "<<Tlis[i].s<<"\n";}cout<<endl;
	}
};
int cmp(R_note a,R_note b){
	if(a.n<b.n) return -1;
	if(a.n>b.n) return 1;
	for(int i=1;i<=a.n;i++){
		int tmp=cmp(a.Tlis[i],b.Tlis[i]);
		if(tmp) return tmp;
	}
	return 0;
}
bool operator < (R_note a,R_note b){
	return cmp(a,b)<0;
}
class DANCE{//点亮我生命的火,火火火火火!
public:
	int N;//数量
	vector<int> c[SIZEN];//邻接表,储存指向它的那些点
	int nxt[SIZEN];
	void Read(void){
		for(int i=1;i<=N;i++){
			scanf("%d",&nxt[i]);
			c[nxt[i]].push_back(i);
		}
	}
	char BR_lis[SIZEN][SIZEL];//相当于括号序列的内存池
	vector<T_note> son[SIZEN];//每个点诸子节点的括号序列
	bool vis[SIZEN];//一个点的括号序列是否被计算
	T_note Calc_Tree(int x){//计算以x为根的外向树的括号序列
		vis[x]=true;
		for(int i=0;i<c[x].size();i++){
			int u=c[x][i];
			if(vis[u]) continue;
			son[x].push_back(Calc_Tree(u));
		}
		T_note T;
		T.s=BR_lis[x];
		sort(son[x].begin(),son[x].end());
		T.s[0]='(';T.len=1;
		for(int i=0;i<son[x].size();i++){
			strncpy(T.s+T.len,son[x][i].s,son[x][i].len);
			T.len+=son[x][i].len;
		}
		T.s[T.len++]=')';
		T.s[T.len]='\0';
		return T;
	}
	T_note OTree[SIZEN][SIZEN];//相当于环的内存池
	int RN;
	R_note Rlis[SIZEN];//基环从小到大排序
	bool vis1[SIZEN];//是否被找过环
	int Find_Cir(int x){
		vis1[x]=true;
		if(vis1[nxt[x]]) return nxt[x];
		return Find_Cir(nxt[x]);
	}
	R_note Calc_Ring(int x){//计算x所在子图
		int u=Find_Cir(x),v;
		R_note R;
		R.n=0,R.Tlis=OTree[x];
		v=u;
		do{vis[v=nxt[v]]=true;}while(v!=u);
		v=u;
		do{R.Tlis[++R.n]=Calc_Tree(v=nxt[v]);}while(v!=u);
		sort(R.Tlis+1,R.Tlis+1+R.n);
		return R;
	}
	void Get_Ring(void){
		for(int i=1;i<=N;i++){
			if(!vis[i]) Rlis[++RN]=Calc_Ring(i);
		}
		sort(Rlis+1,Rlis+1+RN);
	}
	void Clear(void){
		for(int i=0;i<SIZEN;i++) c[i].clear(),son[i].clear();
		memset(vis,0,sizeof(vis));
		memset(vis1,0,sizeof(vis1));
		RN=0;
	}
	void print(void){
		cout<<RN<<endl;
		for(int i=1;i<=RN;i++) Rlis[i].print();cout<<endl;
	}
};
bool operator == (DANCE &G,DANCE &H){
	if(G.N!=H.N) return false;
	if(G.RN!=H.RN) return false;
	for(int i=1;i<=G.RN;i++)
		if(cmp(G.Rlis[i],H.Rlis[i])) return false;
	return true;
}
DANCE G,H;
int main(){
	freopen("pch.in","r",stdin);
	freopen("pch.out","w",stdout);
	int T,n;scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		G.N=H.N=n;
		G.Clear();H.Clear();
		G.Read();H.Read();
		G.Get_Ring();H.Get_Ring();
		if(G==H) printf("T\n");
		else printf("N\n");
	}
	return 0;
}