[WZOI2011 S3]消息传递

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 messagew.in 输出文件 messagew.out
Problem 2 消息传递 (messagew.pas/c/cpp)
问题描述
WZland开办了一个俱乐部(这里面可以干任何的事情),这引来了许多的人来加入。俱乐部的人数越来越多,关系也越来越复杂……
俱乐部的人来自各个地方,为了增加友谊,俱乐部举行了一次晚会。晚会上又进行了一个传话游戏,如果A认识B,那么A收到某个消息,就会把这个消息传给B,以及所有A认识的人(如果A认识B,B不一定认识A),所有人从1到N编号。
现在给出所有“认识”关系,俱乐部的负责人WZland的国王想知道一个十分简单的问题:如果A发布一条新消息,那么会不会经过若干次传话后,这个消息传回给了A,1≤A≤N。但是WZland的国王是出了名的数学差,幸好的是你在他的身边,于是他就将这个问题交给你来解决。


输入格式
输入数据中的第一行是两个数N和M,两数之间有一个空格,表示人数和认识关系数。
接下来的M行,每行两个数A和B,表示A认识B(1A, BN,AB)。
输出格式
输出文件中一共有N行,每行一个字符“T”或“F”。第i行如果是“T”,表示i发出一条新消息会传回给i;如果是“F”,表示i发出一条新消息不会传回给i。
样例输入输出
message.in 
4 6
1 2
2 3
4 1
3 1
1 3
2 3
message.out
T
T
T
F


数据规模
对于30%的数据,N≤1000,M≤20000;
对于50%的数据,N≤10000,M≤100000;
对于100%的数据,N≤100000,M≤200000;
认识关系可能会重复给出。
时间限制
1s