P4246 [SHOI2008] Blocked Traffic

One day, due to some kind of time-travel phenomenon, you arrived in the legendary land of tiny people. Its layout is quite peculiar: the entire country's transportation network can be seen as a rectangular grid with $2$ rows and $C$ columns. Each point on the grid represents a city, and there is a road between adjacent cities. Thus there are $2C$ cities and $3C - 2$ roads in total. The traffic situation is terrible. Sometimes, due to congestion, the road between two cities becomes disconnected; it will not be passable again until the congestion clears. As a newcomer, you volunteer to help at the Ministry of Transport. Hearing that you come from a highly advanced world, the minister gladly asks you to write a query response system to save the ailing transportation network. The ministry will provide some traffic information, and your task is to answer queries based on the current traffic situation. The information comes in the following formats: - `Close r1 c1 r2 c2`: the road between the two adjacent cities $(r_1, c_1)$ and $(r_2, c_2)$ is blocked. - `Open r1 c1 r2 c2`: the road between the two adjacent cities $(r_1, c_1)$ and $(r_2, c_2)$ is unblocked. - `Ask r1 c1 r2 c2`: ask whether cities $(r_1, c_1)$ and $(r_2, c_2)$ are connected. If there exists a path that connects the two cities, return `Y`; otherwise return `N`. Note: $r_i$ denotes the row index and $c_i$ denotes the column index, with $1 \leq r_i \leq 2$ and $1 \leq c_i \leq C$.

The first line contains a single integer $C$, the number of columns in the grid. The following lines each contain one traffic instruction, and a single line `Exit` marks the end of input. Initially, all roads are assumed to be blocked. It is guaranteed that $C \leq 100000$ and the number of instructions $\leq 100000$.

For each query, output a single `Y` or `N`.

Constraints: For $100\%$ of the testdata, $1 \leq C \leq 100000$, and $1 \leq$ number of instructions $\leq 100000$. Translated by ChatGPT 5