小美认为,在人际交往中,但是随着时间的流逝,朋友的关系也是会慢慢变淡的,最终朋友关系就淡忘了。
现在初始有一些朋友关系,存在一些事件会导致两个人淡忘了他们的朋友关系。小美想知道某一时刻中,某两人是否可以通过朋友介绍互相认识?
事件共有 2 种:
1 u v:代表编号 u 的人和编号 v 的人淡忘了他们的朋友关系。
2 u v:代表小美查询编号 u 的人和编号 v 的人是否能通过朋友介绍互相认识。
注:介绍可以有多层,比如 2 号把 1 号介绍给 3 号,然后 3 号再把 1 号介绍给 4 号,这样 1 号和 4 号就认识了。
第一行输入三个正整数n, m, q,代表总人数,初始的朋友关系数量,发生的事件数量。
接下来的m行,每行输入两个正整数u, v,代表初始编号u的人和编号v的人是朋友关系。
接下来的q行,每行输入三个正整数op, u, v,含义如题目描述所述。
1 <= n <= 10^9
1 <= m, q <= 10^5
1 <= u, v <= n
1 <= op <= 2
对于每次 2 号操作,输出一行字符串代表查询的答案。如果编号 u 的人和编号 v 的人能通过朋友介绍互相认识,则输出"Yes"。否则输出"No"。
5 3 5 1 2 2 3 4 5 1 1 5 2 1 3 2 1 4 1 1 2 2 1 3
Yes No No
第一次事件,1 号和 5 号本来就不是朋友,所以无事发生。
第二次事件是询问,1 号和 3 号可以通过 2 号的介绍认识。
第三次事件是询问,显然 1 号和 4 号无法互相认识。
第四次事件,1 号和 2 号淡忘了。
第五次事件,此时 1 号无法再经过 2 号和 3 号互相认识了。
时间限制: c/c++/go: 2s; java: 6.5s; 其他语言: 5s.
选择合适的字体大小
选择合适的主题