Wakanda Forever

题意翻译

某国家有$n$个城市 ，现在要求你把他们两两分组。 每个城市$a_i$和另一个城市$a_j$分成同一组时，$a_i$需要使用$c[i][j]$的费用，对于$a_j$则是$c[j][i]$。 一个合法的分组不能有下面情况： 两个不在同一组的城市$a_x$和$a_y$，在他们之间修一条路的费用在$a_x$的视角下，比当前分组的费用少且在$a_y$的视角下，也比当前分组的费用少。 如果能合法地分组，给出方案，不能输出$-1$。

题目描述

In the Kingdom of Wakanda, the 2020 economic crisis has made a great impact on each city and its surrounding area. Cities have made a plan to build a fast train rail between them to boost the economy, but because of the insufficient funds, each city can only build a rail with one other city, and they want to do it together. Cities which are paired up in the plan will share the cost of building the rail between them, and one city might need to pay more than the other. Each city knows the estimated cost of building their part of the rail to every other city. One city can not have the same cost of building the rail with two different cities. If in a plan, there are two cities that are not connected, but the cost to create a rail between them is lower for each of them than the cost to build the rail with their current pairs, then that plan is not acceptable and the collaboration won't go on. Your task is to create a suitable plan for the cities (pairing of the cities) or say that such plan doesn't exist.

输入输出格式

输入格式

First line contains one integer $ N \;(2 \leq N \leq 10^3)\, $ — the number of cities. Each of the next $ N $ lines contains $ N-1 $ integers $ A_{i,1}, A_{i,2}, ..., A_{i,i-1}, A_{i,i+1}, ..., A_{i,N-1}\; (1 \leq A_{i,j} \leq 10^9)\, $ — where $ A_{i,j} $ represents the cost for city $ i $ to build the rail to city $ j $ . Note that in each line $ A_{i,i} $ is skipped.

输出格式

Output should contain $ N $ integers $ O_{1}, O_{2}, ..., O_N $ , where $ O_i $ represents the city with which city $ i $ should build the rail with, or $ -1 $ if it is not possible to find the stable pairing.

输入输出样例

输入样例 #1

4
35 19 20
76 14 75
23 43 78
14 76 98

输出样例 #1

3
4
1
2

输入样例 #2

4
2 5 8
7 1 12
4 6 7
8 4 5

输出样例 #2

-1

题意翻译

某国家有$n$个城市 ，现在要求你把他们两两分组。 每个城市$a_i$和另一个城市$a_j$分成同一组时，$a_i$需要使用$c[i][j]$的费用，对于$a_j$则是$c[j][i]$。 一个合法的分组不能有下面情况： 两个不在同一组的城市$a_x$和$a_y$，在他们之间修一条路的费用在$a_x$的视角下，比当前分组的费用少且在$a_y$的视角下，也比当前分组的费用少。 如果能合法地分组，给出方案，不能输出$-1$。