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 翻译