Score : $600$ points

问题陈述

在二维平面上有 $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, 2, \ldots, N)$ 满足以下条件。如果存在这样的 $R$，请找出一个。

• 对于从 $1$ 到 $N$ 的每个整数 $i$，让线段 $i$ 是连接 $P_i$ 和 $Q_{R_i}$ 的线段。那么，线段 $i$ 和线段 $j$ $(1 \leq i < j \leq N)$ 永远不会相交。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

There are $2N$ points $P_1,P_2,\ldots,P_N, Q_1,Q_2,\ldots,Q_N$ on a two-dimensional plane. The coordinates of $P_i$ are $(A_i, B_i)$, and the coordinates of $Q_i$ are $(C_i, D_i)$. No three different points lie on the same straight line.

Determine whether there exists a permutation $R = (R_1, R_2, \ldots, R_N)$ of $(1, 2, \ldots, N)$ that satisfies the following condition. If such an $R$ exists, find one.

• For each integer $i$ from $1$ through $N$, let segment $i$ be the line segment connecting $P_i$ and $Q_{R_i}$. Then, segment $i$ and segment $j$ $(1 \leq i < j \leq N)$ never intersect.

Constraints

• $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)$
• No three different points lie on the same straight line.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$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$

Output

If there is no $R$ satisfying the condition, print -1.

If such an $R$ exists, print $R_1, R_2, \ldots, R_N$ separated by spaces. If there are multiple solutions, you may print any of them.

Sample Input 1

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

Sample Output 1

2 1 3

The points are arranged as shown in the following figure.

By setting $R = (2, 1, 3)$, the three line segments do not cross each other. Also, any of $R = (1, 2, 3)$, $(1, 3, 2)$, $(2, 3, 1)$, and $(3, 1, 2)$ is a valid answer.

Sample Input 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

Sample Output 2

3 5 8 2 7 4 6 1