人工湖

成绩 开启时间 2014年09月19日 星期五 10:08
折扣 0.8 折扣时间 2014年09月26日 星期五 10:08
允许迟交 是 关闭时间 2014年09月26日 星期五 10:08
输入文件 lakee.in 输出文件 lakee.out

【题目描述】

有一个湖，他的周围都是城市，每个城市都只和他相邻的两个城市有道路相连。假设有n个城市，编号1-n，公路是双向的，公路有时候是好的，有时候是坏的，现在询问你两个城市是否可以互相到达。

【输入格式】

第一行两个数，一个2<=n<=100000  和 1<=m<=100000，分别代表城市数目和询问次数；接下来m行，每一行三个数f，a，b。f=0时，如果公路a，b之间的道路之前是好的，现在就变成坏的，如果之前是坏的，现在就变成好的。f=1时，询问a，b两个城市是否可以互相到达。

【输出格式】

对于每一个f=1的询问，能到达输出“YES”，否则输出"NO".

【样例输入】

5 10 

1 2 5
0 4 5
1 4 5
0 2 3
1 3 4
1 1 3
0 1 2
0 2 3
1 2 4
1 2 5

【样例输出】 

YES
YES
YES
NO
YES
NO

【提示】

30%   2<=n,m<=100

50%   2<=n,m<=10000

100%  2<=n,m<=100000

【来源】

@高哥