시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 256 MB 3 2 2 66.667%

문제

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.

예제 입력 1

1
1 1
1 2
2 1

예제 출력 1

NG
OK
OK

예제 입력 2

2
1 1
1 2
2 2
2 3
3 3

예제 출력 2

OK
NG
OK
NG
OK

예제 입력 3

2
1 1
1 2
3 3
4 4
4 5

예제 출력 3

NG
NG
OK
NG
NG