19520번 - 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.