AT_arc045_d [ARC045D] みんな仲良し高橋君

在二维坐标平面上，给定 $2N+1$ 个坐标各不相同的点。 高桥君想从这些点中组成尽可能多的“好朋友配对”。 满足以下条件的两点可以组成好朋友配对： - 两个点的 $x$ 坐标或 $y$ 坐标中有一个相等。 但是，每个点最多只能与一个点组成好朋友配对。 高桥君本来想让所有点都组成好朋友配对，但由于点的数量是奇数，这是不可能的。 因此，他决定删除其中任意一个点，然后判断剩下的 $2N$ 个点能否恰好组成 $N$ 组好朋友配对，使所有点都被配对。 请对于每一个点，判断删除该点后，剩下的 $2N$ 个点能否组成 $N$ 组好朋友配对。

输入通过标准输入给出，格式如下： > $N$ > $X_1$ $Y_1$ > $X_2$ $Y_2$ > $\vdots$ > $X_{2N+1}$ $Y_{2N+1}$ - 第 $1$ 行给出一个整数 $N$，表示点的数量满足 $2N+1$。 - 接下来的 $2N+1$ 行，每行包含两个用空格分隔的整数 $X_i$、$Y_i$，表示第 $i$ 个点的坐标为 $(X_i, Y_i)$。 - 对于任意 $i \neq j$，都有 $X_i \neq X_j$ 或 $Y_i \neq Y_j$。

输出应写到标准输出，并以换行结尾。 输出共 $2N+1$ 行。 第 $i$ 行，如果删除第 $i$ 个点后，剩下的 $2N$ 个点可以组成 $N$ 组好朋友配对，则输出 `OK`，否则输出 `NG`。

### 部分分 对于满足以下额外限制的数据集，答对可获得 $30$ 分： - 对所有 $i(1 \leq i \leq 2N)$，都有 $X_i = X_{i+1}$ 或 $Y_i = Y_{i+1}$。 ### 样例解释 2 该输入输出样例满足部分分的限制。 由 ChatGPT 4.1 翻译