Dynamic Road Network of H City

Mayor Xiao Lan of H City is planning the road construction for her city using design software. She can build a bidirectional road between any two areas by selecting them. However, due to budget fluctuations and other factors, roads may be removed after being built. At any moment, she would like to know whether two given areas are connected by a sequence of roads.

More formally, there are n areas and m operations. Each operation is one of the following types:

• ADD u v: Build a road between area u and area v.
• REMOVE u v: Remove a previously built road between area u and area v. It is guaranteed that such a road exists at the time of removal.
• QUERY u v: Determine whether there is a path (possibly composed of several roads) connecting area u and area v. Output YES or NO accordingly.

You are to process these operations in the given order. Note that the road network is dynamic because roads can be both added and removed.

The underlying idea can be modeled by dynamic connectivity. One efficient solution uses an offline approach combined with a segment tree and a Disjoint Set Union (DSU) data structure with rollback capability. The union operation is applied when an edge (road) is active, and rollbacks are performed when leaving a segment of time. A useful formula in DSU analysis is the union by size, ensuring that the time complexity is approximately O(m log m) in the worst case.

The DSU structure satisfies the following recurrence after a union operation: \[ \text{size}(\text{root}) \gets \text{size}(\text{root}) + \text{size}(\text{child}) \]

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 10⁵) representing the number of areas and the number of operations respectively.

Each of the next m lines contains an operation in one of the formats:

• ADD u v
• REMOVE u v
• QUERY u v

It is guaranteed that every REMOVE operation corresponds to a previously performed ADD operation that has not yet been removed.

outputFormat

For each QUERY operation in the input, output a single line containing YES if the two areas are connected, or NO if they are not.

sample

3 2
ADD 1 2
QUERY 1 2

YES