记录编号	168027	评测结果	AAAAAAAAAA
题目名称	[WZOI 2011 S3] 消息传递	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.249 s
提交时间	2015-06-30 13:38:49	内存使用	8.68 MiB

/***********************************************************************/
/**********************By Asm.Def-Wu Jiaxin*****************************/
/***********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
using namespace std;
#define SetFile(x) ( freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) );
#define UseFREAD
#ifdef UseFREAD
#define getc() *(file_ptr++)
#define FreadLenth 5000000
char CHARPOOL[FreadLenth], *file_ptr = CHARPOOL;
#else
#define getc() getchar() 
#endif
#ifdef DEBUG
#include <ctime>
#endif
template<class T>inline void getd(T &x){
	char ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')ch = getc(), neg = true;
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/***********************************************************************/
const int maxn = 100003;

int *adj[maxn], Min[maxn], d[maxn], u[maxn<<1], v[maxn<<1], N, M, vis[maxn], St[maxn], *top = St;
bool scc[maxn], inS[maxn];

inline void init(){
	getd(N), getd(M);
	int i, it[maxn] = {0};
	for(i = 0;i < M;++i){
		getd(u[i]), getd(v[i]);
		++d[u[i]];
	}
	for(i = 1;i <= N;++i)adj[i] = (int*)malloc(sizeof(int) * d[i]);
	for(i = 0;i < M;++i)adj[u[i]][it[u[i]]++] = v[i];
}

void dfs(int cur){
	static int id = 0;
	inS[cur] = true;*(top++) = cur;
	Min[cur] = vis[cur] = ++id;
	for(int i = 0, to;i < d[cur];++i){
		to = adj[cur][i];
		if(!vis[to])dfs(to), Min[cur] = min(Min[cur], Min[to]);
		else if(inS[to])Min[cur] = min(Min[cur], Min[to]);
	}
	if(Min[cur] != vis[cur])return;
	if(*(top-1) == cur){--top, inS[cur] = false;return;}
	do{inS[*--top] = false, scc[*top] = true;}while(*top != cur);
}

inline void work(){
	int i;
	for(i = 1;i <= N;++i)if(!vis[i])dfs(i);
	for(i = 1;i <= N;++i)puts(scc[i] ? "T" : "F");
}

int main(){

#ifdef DEBUG
	freopen("test.txt", "r", stdin);
#elif !defined ONLINE_JUDGE
	SetFile(messagew);
#endif

#ifdef UseFREAD
	fread(file_ptr, 1, FreadLenth, stdin);
#endif

	init();
	work();

#ifdef DEBUG
	printf("\n%.3lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}