← 返回题目列表

Codeforces · 1423/A

A. 永远的瓦坎达

中文机器翻译题面 查看原题

在瓦坎达王国,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$$$。

示例

输入 #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