DYNACON2 - Dynamic Graph Connectivity

no tags 

 

A graph initially consists of N (1 ≤ N ≤ 100,000) unconnected vertices. The vertices are numbered from 1 to N.

Your task is to maintain that graph 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 vertices 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:
4 11
add 1 2
add 2 3
add 3 4
add 1 4
conn 4 2
rem 1 2
conn 2 4
rem 3 4
conn 4 2
add 2 4
conn 4 2

Output:
YES
YES
NO
YES

This example will be the first test case.

hide comments
petkov: 2019-03-01 17:54:05

The constrains are not too tight. I solved it with segment tree + partially persistent dsu. You don't need link/cut trees.

tanavya: 2017-12-08 20:25:29

TLE :( constraints too tight.

dacin21: 2016-01-10 20:52:26

For those who want a challenge, one can actually solve this problem using an on-line algorithm (answer each querry before you read the next one)! Because that's what i did.

immortalco: 2015-10-04 10:54:46

The problem description is wrong.
- add A B : add an edge between vertices A and B, where initially there is no path between A and B.
+ add A B : add an edge between vertices A and B, where initially there is no EDGE between A and B.

immortalco: 2015-10-04 10:52:58

A tough task.
I used Segment-Tree Divide-and-Conquer with president disjoint set to solve, but got TLE.
Then I replaced disjoint set with link/cut trees, AC.

jkelava6: 2015-01-04 14:09:10

"where initially there is no path between A and B" - but first 4 commands of the example form a square. "add 1 4" breaks that rule! Please fix!

Last edit: 2015-01-04 14:22:13

Added by:Andrey Naumenko
Date:2011-09-22
Time limit:0.347s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64