人工湖

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file lakee.in Output file 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

【来源】

@高哥