If we connect the points that share one coordinate, the points will be divided into cycles and paths. With paths, it is clear which points should be connected with line segments. If there is a path with an odd number of points, we immediately conclude that the answer is NE. For cycles, we must determine whether we will draw all horizontal or all vertical lines (in the rest of the editorial we call this orientation).

There are at most ~N/4~ cycles, so in a subtask where ~N \le 40~ we can try all ~2^\text{number of cycles}~ possible cycle orientations and check if there is one where line segments don't intersect.

The main idea is as follows: at the beginning, the paths determine some line segments that must be drawn. These line segments determine the orientations of those cycles that they intersect, which determine the orientations of some other cycles, etc. If at some point during this process we draw a line segment that intersects some line segment that is already drawn or we conclude that both cycle orientations are invalid, then the answer is NE.

For a subtask where ~N \le 2000~, we can do that in ~\mathcal O(N^2)~:

First, we find all paths and cycles and place all line segments from paths into a FIFO queue of the lines that need to be drawn. While the queue is not empty, we pop a line segment from it and check whether it intersects any of the previously drawn line segments (then the answer is NE). Then we traverse over not-yet-oriented cycles and orient those cycles which intersect with the line segment we are about to draw (orientation of the cycle needs to be different than the orientation of the line segment). In the end, we might have some leftover cycles which we can orient in the same orientation (doesn't matter which one).

For the final subtask where ~N \le 10^5~, we need to check those line segment intersections more efficiently. We will use a segment tree to devise a data structure which supports the following operations:

• add a line segment ~(x_1, y)~ – ~(x_2, y)~
• remove a previously added line segment ~(x_1, y)~ – ~(x_2, y)~
• determine for some ~x~ and ~y_1~ what is the smallest ~y_2 \ge y_1~ such that there exists a line segment with ~y~ coordinate equal to ~y_2~ which contains the point ~(x, y_2)~ (or determine that no such ~y_2~ exists)

In each node of the segment tree, we will store a set of all ~y~ coordinates whose ~x~ coordinates are in an interval for which that node is responsible. The first two operations boil down to standard addition/deletion of ~y~ to corresponding nodes. To answer the third operation, we will find such ~y_2~ for each node responsible for ~x~ (e.g. by using lower_bound in std::set) and return minimal such value. The complexity of all three operations is ~\mathcal O(\log^2 N)~.

Line segment which intersects the line segment ~(x, y_1)~ – ~(x, y_2)~ exists if the answer to the third query for ~x~ and ~y_1~ is less than or equal to ~y_2~.

We will use two such data structures – one for horizontal and one for vertical line segments – in which we will store the line segments of not-yet-oriented cycles and two additional data structures to store already drawn line segments. We leave out the rest of the details as an exercise to the reader.