CF1423A Wakanda Forever

在瓦坎达王国，2020 年的经济危机对每个城市及其周边地区产生了巨大影响。各城市计划在它们之间修建高速铁路以促进经济发展，但由于资金不足，每个城市只能与另一个城市共同修建一条铁路，并且希望共同承担修建费用。 在计划中配对的城市将共同分担它们之间铁路的建设费用，但一个城市可能需要比另一个城市支付更多。每个城市都知道自己与其他每个城市之间修建铁路的预估费用。一个城市与不同城市修建铁路的费用不能相同。 如果在某个方案中，存在两座未连接的城市，但它们之间修建铁路的费用对双方来说都低于各自与当前配对城市的费用，则该方案不可接受，合作将无法进行。你的任务是为这些城市制定一个合适的配对方案（即城市之间的配对），或者说明不存在这样的方案。

第一行包含一个整数 $N\;(2 \leq N \leq 10^3)$，表示城市的数量。 接下来的 $N$ 行，每行包含 $N-1$ 个整数 $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)$，其中 $A_{i,j}$ 表示城市 $i$ 与城市 $j$ 修建铁路的费用。注意每行中跳过了 $A_{i,i}$。

输出应包含 $N$ 个整数 $O_{1}, O_{2}, ..., O_N$，其中 $O_i$ 表示城市 $i$ 应与之修建铁路的城市编号。如果无法找到稳定的配对方案，则输出 $-1$。

由 ChatGPT 4.1 翻译