#Psmt17. 3.生物进化

3.生物进化

3.生物进化

题目描述

生物学家们发现了几种动物化石。他们将化石依次编号为1,2,3,...n-1,n。

经过简单的分析,他们发现了一些规律:若动物A是由动物B经过若干次进化而成的,则称B是A的祖先,特别地,任意一种动物都是它自己的祖先(经过0次进化);若动物A是由动物B经过一次进化而成的,则称B是A的直系祖先;1号动物无直系祖先,其它每种动物都有且仅有一个直系祖先;发现的动物化石中,号的是它们共同的祖先;所有的动物都是从低级向高级进化。

为了进一步确定生物进化的过程,生物学家们经过复杂的分析和计算,得出这些化石两两间的“差异程度”。“差异程度”有如下性质:对于两个物种i,j,它们的“差异程度”是一个非负整数,记为Di,jD_{i,j};Di,i,i=j时,Di,j=Dj,i=0D_{i,i},i=j时,D_{i,j}=D_{j,i}=0;若i是k的祖先,k是j的祖先则Di,j=Di,k+Dk,jD_{i,j}=D_{i,k}+D_{k,j};若k是i和j的所有公共祖先中最高级的,则Di,j=Di,k+Dk,jD_{i,j}=D_{i,k}+D_{k,j}。因此,利用“差异程度”,就可以确定生物进化的过程。

但是化石数量实在太多了,于是,生物学家们希望你能够帮助他们。

输入格式

第一行是一个整数n,表示化石种类数。

接下来n行,每行个n整数,第i行第j个是Di,jD_{i,j},表示i和j的“差异程度”。

输出格式

n-1行,第i行是一个整数,表示i+1号动物的直系祖先为C。

数据范围

(原站未提供,导入后需人工补齐)

样例

4
0 1 4 7
1 0 5 8
4 5 0 3
7 8 3 0
1
1
3

提示

对于100%的数据:1<=n<=100,0<=Di,jD_{i,j}<=100000。