← 返回题目列表

Codeforces · 579/B

B. 寻找团队成员

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

有一个名为 SnakeUp 的编程竞赛,有 2n 个人想参加。为了参加这项比赛,人们需要组成恰好由两人组成的团队。您将获得两个人每种可能组合的力量。所有优势的价值都是不同的。

每个参赛者都希望自己能找到一个队友,让自己的队伍实力尽可能的高。即参赛者从愿意与自己组队的队友中选择一名队友,组成一支实力最强的队伍。更正式地说,如果 A 和 B 两个人都是另一个人的最佳队友(在未配对的参赛者中),则他们可以组成一个团队。

你能确定谁将成为每个人的队友吗?

输入

输入中有 2n 行。

第一行包含一个整数 n (1 ≤ n ≤ 400) — 要组建的团队数量。

第 i 行 (i > 1) 包含 i - 1 个数字 ai1, ai2, ... , ai(i - 1)。这里aij(1≤aij≤106,所有aij都不同)表示i和j(从1开始编号)组成的团队的实力。

输出

输出包含 2n 个数字的行。第i个数字应该代表第i个人的队友数量。

示例

输入 #1

2
6
1 2
3 4 5

输出 #1

2 1 4 3

输入 #2

3
487060
3831 161856
845957 794650 976977
83847 50566 691206 498447
698377 156232 59015 382455 626960

输出 #2

6 5 4 3 2 1

注意

在第一个样本中,参赛者 1 和 2 将是队友,参赛者 3 和 4 也是队友,因此参赛者 1、2、3、4 的队友将分别是 2、1、4、3。