#Psmt17. 3.生物进化
3.生物进化
3.生物进化
题目描述
生物学家们发现了几种动物化石。他们将化石依次编号为1,2,3,...n-1,n。
经过简单的分析,他们发现了一些规律:若动物A是由动物B经过若干次进化而成的,则称B是A的祖先,特别地,任意一种动物都是它自己的祖先(经过0次进化);若动物A是由动物B经过一次进化而成的,则称B是A的直系祖先;1号动物无直系祖先,其它每种动物都有且仅有一个直系祖先;发现的动物化石中,号的是它们共同的祖先;所有的动物都是从低级向高级进化。
为了进一步确定生物进化的过程,生物学家们经过复杂的分析和计算,得出这些化石两两间的“差异程度”。“差异程度”有如下性质:对于两个物种i,j,它们的“差异程度”是一个非负整数,记为;;若i是k的祖先,k是j的祖先则;若k是i和j的所有公共祖先中最高级的,则。因此,利用“差异程度”,就可以确定生物进化的过程。
但是化石数量实在太多了,于是,生物学家们希望你能够帮助他们。
输入格式
第一行是一个整数n,表示化石种类数。
接下来n行,每行个n整数,第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<=<=100000。