AT_abc373_g.[ABC373G] No Cross Matching

在二维平面上有 $2N$ 个点，分别为 $P_1,P_2,\ldots,P_N$ 和 $Q_1,Q_2,\ldots,Q_N$。点 $P_i$ 的坐标为 $(A_i,B_i)$，点 $Q_i$ 的坐标为 $(C_i,D_i)$。不存在同一直线上的三个不同点。

请判断是否存在一个数列 $R=(R_1,R_2,\ldots,R_N)$，它是 $1$ 到 $N$ 的一个排列，并且满足以下条件：

• 对于所有 $1$ 到 $N$ 的整数 $i$，将 $P_i$ 和 $Q_{R_i}$ 作为端点连成线段，要求任意两条线段 $i$ 和 $j$（$1\leq i<j\leq N$）都不相交。

如果存在这样的 $R$，请给出其中一个；如果不存在，输出 $-1$。

输入通过标准输入给出，格式如下：

$N$
$A_1\ B_1$
$A_2\ B_2$
$\vdots$
$A_N\ B_N$
$C_1\ D_1$
$C_2\ D_2$
$\vdots$
$C_N\ D_N$

如果不存在满足条件的 $R$，输出 $-1$。

如果存在，输出 $R_1,R_2,\ldots,R_N$，用空格分隔。若有多个答案，输出任意一个均可。

数据范围

• $1\leq N\leq 300$
• $0\leq A_i,B_i,C_i,D_i\leq 5000$（$1\leq i\leq N$）
• $(A_i,B_i)\neq(A_j,B_j)$（$1\leq i<j\leq N$）
• $(C_i,D_i)\neq(C_j,D_j)$（$1\leq i<j\leq N$）
• $(A_i,B_i)\neq(C_j,D_j)$（$1\leq i,j\leq N$）
• 不存在同一直线上的三个不同点
• 所有输入均为整数

样例解释 1

点的分布如下图所示。

取 $R=(2,1,3)$ 时，三条线段互不相交。实际上，$R$ 取 $(1,2,3)$、$(1,3,2)$、$(2,3,1)$、$(3,1,2)$ 也都是正确答案。

由 ChatGPT 4.1 翻译