# Dynamic Connectivity

Time limit: 0.75s Memory limit: 128MB Input: Output:

The capital of the United States, Washington DC, was first established hundreds of years ago. At first, not all land was connected - all pieces of land were actually surrounded by water and were inaccesible from one another without sailing. Over time, more and more 2-way roads have been built over water (e. g. bridges). At the same time, some of these roads were also destroyed (e.g. during wars) or otherwise made inaccesible (e.g. floods, earthquakes, landslides). A historian builds a record of all roads that were ever built or destroyed - chronologically. He also sometimes asks - were land X and land Y connected by roads at this point in time? He begs you for help in answering his queries.

## Input data

In order to help you, the historian has assigned a unique number to each piece of land. There are $n$ such pieces, indexed from $1$ to $n$. His record also contains $m$ entries. The first line contains integers $n$ and $m$, followed by $m$ entries - each on a new line. Each such entry will have one of the following three types:

• + a b: A road between a and b has been built. It is guaranteed it didn't already exist.
• - a b: The road between a and b has been destroyed. It is guaranteed it existed.
• ? a b: Can you reach land b from land a without sailing?

## Output data

For each query of type $?$, output a line $Y$ or $N$ indicating whether $a$ and $b$ were connected.

## Constraints and clarifications

• $1 \leq n \leq 5 \ 000$
• $1 \leq m \leq 100 \ 000$

## Example 1

stdin

300 5
? 23 37
+ 23 37
? 23 37
- 37 23
? 23 37


stdout

N
Y
N


## Example 2

stdin

4 10
+ 1 2
+ 2 3
+ 3 1
? 1 4
+ 4 3
? 1 4
- 2 3
? 1 4
- 1 3
? 1 4


stdout

N
Y
Y
N