PID727 / 亲戚 Relative
题目描述

【问题描述】

老爸出差了,你和你的妈妈准备去走人家,但是你的亲戚们数量太多了,关系网过於庞大,要判断两个是否是亲戚,确实还很不容易,现在给出一些消息,你想知道某两人是否是亲戚关系

规定:如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚,

如:x和y是亲戚,y和z是亲戚,那么x和z也是亲戚。

但是由于亲戚们的感情并不是总是那么好的,所以随时会出现反目的现象。倘若某对亲戚反目了,x的亲戚和y的亲戚也就不再是亲戚。

如:x,y反目了,y,z是亲戚,x,z就不是亲戚。

由于亲戚们的性格不是那么好(有点2),所以他们在反目之后就不会再和好。他们各自的亲戚们也不会再成亲戚。

如:x和y反目了,x的亲戚就不会和y的亲戚再成亲戚关系。

在这里,只有直接的亲戚才会反目(废话,不直接的亲戚他们认都不认识,怎么会反目?!)同时我们保证不存在有一个人两难的情况

两难:假设z既是x的直接亲戚,又是y的直接亲戚,那x和y反目后,z就会出现两难的情况。

另外,我们规定自己是自己的亲戚。

输入格式

第一行包含两个正整数n、q、m分别表示有n个人,q对亲戚,m个消息

以下m行:每行两个数Mi,Mj(1<=Mi,Mj<=N),表示Mi和Mj是亲戚。

接着q行,每行一个字符串C和两个数Mi,Mj(1<=Mi,Mj<=N)

如果C=’A’,表示询问Mi和Mj是否为亲戚。

如果C=’F’,表示Mi和Mj反目了(保证Mi和Mj是直接亲戚关系)

输出格式

若干行,对于每个询问输出’Yes’表示他们是亲戚,或’No’表示他们不是亲戚

样例输入
样例输出
注释

【数据规模及约定】

对于20%的数据满足n,m≤10,q≤50;

对于30%的数据,没有亲戚反目。

对于50%的数据满足n,m≤1000,q≤10000。

对于100%的数据满足1≤n,m≤10000,1≤q≤100000;

提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论