DYNACON1 - Dynamic Tree Connectivity
A forest of unrooted trees initially consists of N (1 ≤ N ≤ 100,000) single-vertex 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 single-vertex 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
This example will be the first test case.
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
hide comments
Problem Solver:
2012-08-18 10:55:53
There is very similiar task around : http://www.spoj.pl/problems/DYNALCA/ |
Added by: | indy256 |
Date: | 2011-09-23 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |