P10665 [AMPPZ2013] Bytehattan

Bytehattan has $n \times n$ grid points, forming a grid graph. At the beginning, the whole graph is complete. There are $k$ operations. In each operation, an edge $(u,v)$ in the graph is deleted. You need to answer whether $u$ and $v$ are still connected after deleting this edge.

The first line contains two positive integers $n,k(2\leq n\leq 1500,1\leq k\leq 2n(n-1))$, representing the size of the grid graph and the number of operations. The next $k$ lines describe the operations. Each line contains two pieces of information. Each piece of information contains two positive integers $a,b(1\leq a,b\leq n)$ and a character $c$ ($c$ is `N` or `E`). If $c$ is `N`, it means deleting the edge from $(a,b)$ to $(a,b+1)$. If $c$ is `E`, it means deleting the edge from $(a,b)$ to $(a+1,b)$. The data is encrypted. For each operation, if the previous answer was TAK or this is the first operation, only consider the first piece of information; otherwise, only consider the second piece of information. The data guarantees that each edge is deleted at most once.

Output $k$ lines. For each query, if the two endpoints are still connected, output TAK; otherwise output NIE.

Constraints: $2\leq n\leq 1500$, $1\leq k\leq 2n(n-1)$, $1\leq a,b\leq n$. Translated by ChatGPT 5