AT_pakencamp_2025_day3_c Don't be Clockwise

在二维平面上有 $N$ 个点 $p_1,p_2,\dots,p_N$。 点 $p_i$ 的坐标为 $(X_i,Y_i)$。不会有多个点重叠在同一坐标上。 请对点列 $p=(p_1,p_2,\dots,p_N)$ 进行重排，得到一个新的点列 $q=(q_1,q_2,\dots,q_N)$，使其满足以下条件。或者，若不存在这样的重排，请声明不可能。 - 对于所有 $1\leq i\leq N-2$，点列 $q_i,q_{i+1},q_{i+2}$ 要么共线，要么按照此顺序呈现逆时针方向。 - 更准确地说，设 $q_i$ 的坐标为 $(x_i,y_i)$，则必须满足 $(x_{i+1} - x_i)(y_{i+2} - y_{i+1}) - (y_{i+1} - y_i)(x_{i+2} - x_{i+1}) \ge 0$。 请对 $T$ 组测试数据分别解决上述问题。

输入由标准输入给出，格式如下： > $T$ > $\text{case}_1$ > $\text{case}_2$ > $\vdots$ > $\text{case}_T$ 每组测试数据格式如下： > $N$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\dots$ $X_N$ $Y_N$

输出 $T$ 行。 第 $i$ 行表示第 $i$ 个测试用例的答案。如果不存在满足条件的 $q$，输出 $-1$。 如果存在，设 $q=(p_{r_1},p_{r_2},\dots,p_{r_N})$，则输出 $r_1,r_2,\dots,r_N$，用空格隔开。 如果有多个答案，输出任意一个即可。

### 样例解释 1  ### 数据范围 - $1\leq T\leq 100$ - $3\leq N\leq 3000$ - $0\leq X_i,Y_i\leq 10^9$ - $(X_i,Y_i)\ne (X_j,Y_j)$ ($i\ne j$) - 所有 $N$ 的总和不超过 $3000$ - 所有输入均为整数 由 ChatGPT 5 翻译