Point Pairs

There are $2N+1$ points on a plane. The $i$-th point is at $(X\_i, Y\_i)$. Two points $i$ and $j$ can be paired if $X\_i = X\_j$ or $Y\_i = Y\_j$.

For each point, determine the following:

• If you remove this point from the set of points, you get $2N$ points. Can these $2N$ points be separated into $N$ disjoint pairs?

$N$
$X\_1$ $Y\_1$
$X\_2$ $Y\_2$
$\vdots$
$X\_{2N+1}$ $Y\_{2N+1}$

Output $2N+1$ lines. For the $i$-th line, print "OK" if all points except for the $i$-th can be separated into $N$ disjoint pairs. Otherwise print "NG".

• $1 \leq N \leq 100,000$
• $1 \leq X\_i, Y\_i \leq 2N+1$
• The points are pairwise distinct.
• All values in the input are integers.