记录编号	87758	评测结果	AAAAAAAAAA
题目名称	[WZOI 2011 S3] 消息传递	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	0.522 s
提交时间	2014-02-09 16:12:20	内存使用	4.22 MiB

#include<stdio.h>
#include<vector>
#include<stack>
#include<string.h>
#include<algorithm>

using namespace std;

const int MAXN=100000+10;

bool is_have[MAXN]={0};

struct SCC{
	int pre[MAXN],lowlink[MAXN],sccno[MAXN],dfs_clock,scc_cnt;
	vector<int> G[MAXN];
	
	void init(int n){
		memset(pre,0,sizeof(pre));
		memset(lowlink,0,sizeof(lowlink));
		memset(sccno,0,sizeof(sccno));
		dfs_clock=scc_cnt=0;
	}
	
	stack<int> S;
	
	void dfs(int u){
		pre[u]=lowlink[u]=++dfs_clock;
		S.push(u);
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i];
			if(!pre[v]){
				dfs(v);
				lowlink[u]=min(lowlink[u],lowlink[v]);
			}else if(!sccno[v]){
				lowlink[u]=min(lowlink[u],pre[v]);
			}
		}
		if(lowlink[u]==pre[u]){
			scc_cnt++;
			while(true){
				int x=S.top();S.pop();
				sccno[x]=scc_cnt;
				if(x==u)break;
			}
		}
	}
	
	void find_scc(int n){
		init(n);
		for(int i=1;i<=n;i++){
			if(!pre[i] && is_have[i])dfs(i);
		}
	}
	
	void add_edge(int u,int v){
		G[u].push_back(v);
	}
}solver;


struct edge{
	int u,v;
	int hash;
	edge(){}
	edge(int uu,int vv){
		u=uu;v=vv;hash=0;
		hash=u*u*u*v*(u*u*4321-41324);
	}
	bool operator < (const edge& b){
		 if(hash<b.hash)return hash<b.hash;
	}
	bool operator > (const edge& b){
		 if(hash>b.hash)return hash>b.hash;
	}	
}edges[MAXN];
int read_build(){
	int n,m;
	scanf("%d %d",&n,&m);
	int u,v;
	for(int i=0;i<m;i++){
		scanf("%d %d",&u,&v);
		edges[i]=edge(u,v);
		is_have[u]=is_have[v]=true;
		//solver.add_edge(u,v);
	}
	//sort(edges,edges+m);
	int last_hash=423524;
	for(int i=0;i<m;i++){
		if(edges[i].hash!=last_hash){
			solver.add_edge(edges[i].u,edges[i].v);
			last_hash=edges[i].hash;
		}
	}
	return n;
}
int scc_num[MAXN]={0};
void solve(){
	int n=read_build();
	solver.find_scc(n);
	for(int i=1;i<=n;i++){
		scc_num[solver.sccno[i]]++;
	}
	for(int i=1;i<=n;i++){
		char ans;
		if(scc_num[solver.sccno[i]]>1 && solver.sccno[i]){
			ans='T';
		}else{
			ans='F';
		}
		printf("%c\n",ans);
	}
}

void open(){
	freopen("messagew.in","r",stdin);
	freopen("messagew.out","w",stdout);
}

int main(){
	open();
	solve();
	return 0;
}