問題文
二维坐标平面上的不同坐标 您将获得 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