19520번 - Point Pairs 다국어

문제

There are 2ドルN+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 2ドルN$ points. Can these 2ドルN$ points be separated into $N$ disjoint pairs?

입력

$N$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_{2N+1}$ $Y_{2N+1}$

출력

Output 2ドルN+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.

힌트