无交叉匹配

题目描述

二维平面上有 $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)$。 任意三个不同点不在同一条直线上。

判断是否存在一个 $(1, 2, \ldots, N)$ 的排列 $R = (R_1, R_2, \ldots, R_N)$ 满足以下条件。如果存在，请找出一个。

对每个整数 $i$（从 $1$ 到 $N$），设线段 $i$ 为连接 $P_i$ 和 $Q_{R_i}$ 的线段。则线段 $i$ 和线段 $j$（$1 \leq i \lt j \leq N$）永不相交。

输入格式

输入按以下格式从标准输入给出：

$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$。如果存在多个解，输出其中任意一个即可。

样例

3
0 0
2 4
4 2
0 2
2 0
4 4

2 1 3

令 $R = (2, 1, 3)$，三条线段互不相交。另外，$R = (1, 2, 3)$、$(1, 3, 2)$、$(2, 3, 1)$、$(3, 1, 2)$ 中的任意一个也都是合法答案。

8
59 85
60 57
72 12
3 27
16 58
41 94
77 64
97 20
32 37
7 2
57 94
35 70
38 60
97 100
5 76
38 8

3 5 8 2 7 4 6 1

数据范围

• $1 \le N \le 300$
• $0 \le A_i, B_i, C_i, D_i \le 5000$（$1 \le i \le N$）
• $(A_i, B_i) \neq (A_j, B_j)$（$1 \le i \lt j \le N$）
• $(C_i, D_i) \neq (C_j, D_j)$（$1 \le i \lt j \le N$）
• $(A_i, B_i) \neq (C_j, D_j)$（$1 \le i, j \le N$）
• 任意三个不同点不在同一条直线上
• 输入均为整数

提示

答案不唯一，输出任意合法解即可。