本题没有可用的提交语言。

描述

最近，在金融行业中计算机的使用引起了争议，因为程序化交易——旨在利用价格的极小波动——在许多华尔街公司被禁止。计算机编程的伦理学是一个新兴的领域，存在许多棘手的问题。

套利是将一种货币兑换成另一种货币，目的是利用几种货币之间转换率的微小差异来获取利润。例如，如果1美元兑换0.7英镑，1英镑兑换9.5法郎，1法郎兑换0.16美元，那么一个套利交易员可以从1美元开始，通过1 * 0.7 * 9.5 * 0.16 = 1.064美元来赚取6.4%的利润。

你将编写一个程序来判断一系列货币兑换是否能如上所述获得利润。

为了实现成功的套利，兑换序列必须从同一种货币开始并结束，但可以考虑任何起始货币。

输入

输入文件包含一个或多个转换表。你需要为输入文件中的每个表格解决套利问题。

每个表格前面有一个整数n，单独占一行，表示表格的维度。最大维度为20，最小维度为2。

然后是按行主序排列的表格，但表格的对角线元素缺失（这些元素假定为1.0）。因此，表格的第一行表示国家1与其他n-1个国家之间的转换率，即国家i（2 <= i <= n）可以用国家1的1单位货币兑换到多少单位的货币。

因此，每个表格由n+1行组成：1行包含n，接下来n行表示转换表。

输出

对于输入文件中的每个表格，必须判断是否存在一个兑换序列，结果能获得超过1%的利润（0.01）。如果存在这样一个序列，你必须打印出产生利润的兑换序列。如果存在多个序列能获得超过1%的利润，则必须打印出最短的序列，即使用最少货币交换次数的序列。

由于美国税务局（IRS）关注交易序列过长，所有有利润的序列必须包含n或更少的交易次数，其中n是给出转换率的表格的维度。序列1 2 1表示两次兑换。

如果存在有利润的序列，必须打印出结果的兑换序列。该序列以整数表示，整数i表示转换表中的第i行（即国家i）。序列的第一个整数是套利序列的起始国。该整数也是序列的终止国。

如果不存在任何有利润的序列（在n或更少次交易内），则打印“no arbitrage sequence exists”。

3
1.2 .89
.88 5.1
1.1 0.15
4
3.1    0.0023    0.35
0.21   0.00353   8.13 
200    180.559   10.339
2.11   0.089     0.06111
2
2.0
0.45

 1 2 1
 1 2 4 1
no arbitrage sequence exists

来源

Duke Internet Programming Contest 1990, uva 104