DYNACON1  Dynamic Tree Connectivity
A forest of unrooted trees initially consists of N (1 ≤ N ≤ 100,000) singlevertex trees. The vertices are numbered from 1 to N.
Your task is to maintain that forest and answer connectivity queries.
All edges in the problem are undirected.
You will receive the following queries, where (1 ≤ A, B ≤ N) :
 add A B : add an edge between vertices A and B, where initially there is no path between A and B.
 rem A B : remove edge between vertices A and B, where initially there is an edge between A and B.
 conn A B : print YES if there is a path between A and B and NO otherwise, where A and B are different.
Input
The first line of input contains the number of initial singlevertex trees N and the number of queries M (1 ≤ M ≤ 100,000). The following M lines contain queries.
Output
For each conn query output YES or NO. Pay attention to letter case.
Example
Input:
5 11
conn 1 5
add 1 2
add 1 3
add 3 4
add 5 4
conn 1 5
rem 4 5
conn 1 5
rem 3 4
add 3 5
conn 1 5
Output:
NO
YES
NO
YES
This example will be the first test case.
hide comments
fabijanb:
20190213 20:31:54
very weak test cases, gives AC with a solution that fails on some easy cases 

[Rampage] Blue.Mary:
20160322 16:18:56
Test case is too weak. A silly (LCTlike) bruteforce approach can get AC. 

bakaniner:
20160224 12:47:33
got AC with UnionFind Sets in 0.07s :) 

dacin21:
20151211 18:16:54
Great problem to test my EulerTourTree implementation (although it's armortized O(M*lg^2(N)) ) based on splaytrees!


Chiang sheng wen:
20151208 08:29:10
Finally got Accepted with Link/Cut Tree implemented with Treap! 

ZiYuan:
20120818 10:55:53
Happy to see the time constraint once became 1600s but now drops to 60s Last edit: 20110926 22:38:17 

:D:
20120818 10:55:53
N*N/8 for N=10^5 is 1.25*10^9. That's over a gigabyte in a single array! Memory limit on SPOJ is 256 MB. Even if it was few GB, I'm not sure the system would be able to allocate that big of a structure. 

Bojan Rosko:
20120818 10:55:53
it's giving me sigsegv... I've checked it on ideone.com, and it didn't reported any problems. I have in my code an array of (N*N/8) bytes, but it shouldn't be a problem... 

Siarhei Kulik:
20120818 10:55:53
Why the TL is so huge? It seems that even O(M*N) can pass. There is O(M*lg(M)) solution for any kind of undirected graph, not only for trees. Last edit: 20110925 14:50:34 

xiaodao:
20120818 10:55:53
..But this is a unrooted tree..

Added by:  Andrey Naumenko 
Date:  20110923 
Time limit:  0.395s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 