← 返回题目列表

AtCoder · arc045_d

D. 大家都是好朋友高桥君

中文机器翻译题面 查看原题

問題文

二维坐标平面上的不同坐标 您将获得 2N+1 分。

高桥从这一点上结识了很多好朋友。

满足以下条件的点可以形成良好的配对。

  • 2 两点 使用以下公式定义 x 坐标和 y 任一坐标都相等。

然而,任何一点 2 无法形成超过两点的友好配对。

高桥先生想将所有点都变成好对,但意识到这是不可能的,因为点的数量是奇数。

那么是哪一个? 删除 1 点,然后 N 我想如果我创造了一对好朋友,我就可以让所有的点成为好一对。

对于每个点,如果删除该点,剩余的 从 2N 点开始 N 确定是否可以建立一对好朋友。


入力

输入是按以下格式从标准输入给出的。

N
X_1 Y_1
X_2 Y_2
:
X_{2N+1} Y_{2N+1}
  • 1 行是表示点数的整数。 N(1 ≦ N ≦ 100,000) 。
  • 之后 2N+1 行提供有关点位置的信息。其中 i 行是一个整数 X_i(1 ≦ X_i ≦ 2N+1),\ Y_i(1 ≦ Y_i ≦ 2N+1) 以空格分隔,即 第 i 点的坐标为 (X_i,\ Y_i) 。 如果所有满足
  • i ≠ j 然后,X_i ≠ X_j 或 Y_i ≠ Y_j 满意。

出力

输出应发送到标准输出,并在末尾添加换行符。

输出是 由 2N+1 行组成。 当删除第

i 行中,i 点时,剩余的 2N 点开始 N 如果你能配成一对OK,如果你做不到 应输出NG。

部分点

如果您正确回答了还满足以下约束的数据集: 30 点。

  • 全部 关于 i(1 ≦ i ≦ 2N) , 满足X_i = X_{i+1} 或 Y_i = Y_{i+1} 之一。

入力例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