Connectivity Queries on a Grid Graph

In Bit-Hattan Town there is an \(n\times n\) grid of points which forms a grid graph. Initially, every grid edge exists between adjacent grid points. Two grid points are adjacent if they share a common edge (up, down, left or right). You are given \(k\) operations. In each operation, an existing edge between two grid points \(u\) and \(v\) is removed permanently. After each removal, you need to determine whether vertices \(u\) and \(v) remain connected through a different path in the updated graph.

Note: The vertices are labeled by their grid coordinates in 1-indexed format. Two vertices \( (x_1,y_1) \) and \( (x_2,y_2) \) are adjacent if and only if \(|x_1-x_2|+|y_1-y_2|=1\).

For example, consider a 2x2 grid with vertices:

(1,1)   (1,2)
(2,1)   (2,2)

The edges are between (1,1)-(1,2), (1,1)-(2,1), (1,2)-(2,2) and (2,1)-(2,2). Even if one edge is removed, the two endpoints may still be connected by an alternate route. However, a carefully chosen sequence of deletions may eventually disconnect the endpoints of a removed edge.

inputFormat

The first line contains two integers \(n\) and \(k\) (\(2 \leq n \leq 1000\), \(1 \leq k \leq 100000\)), representing the size of the grid and the number of operations, respectively.

Each of the next \(k\) lines contains four integers \(x_1, y_1, x_2, y_2\) (\(1 \leq x_1, x_2, y_1, y_2 \leq n\)) describing the grid coordinates of the two endpoints of the edge to be removed. It is guaranteed that \((x_1,y_1)\) and \((x_2,y_2)\) are adjacent in the grid.

outputFormat

For each operation, print a single line containing either YES if the two vertices remain connected after the removal of that edge, or NO otherwise.

sample

2 1
1 1 1 2

YES