2371: 生物进化

    在一片茂密的原始森林中，生物学家们发现了几种远古时期的动物化石。他们将化石依次编号为1，2，3，……n-1，n，然后带回实验室。

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

    为了进一步确定生物进化的过程，生物学家们经过复杂的分析和计算，得出这些化石两两间的“差异程度”。“差异程度”有如下性质：对于两个物种i，j，它们的“差异程度”是一个非负整数，记为Dij；Dii=0，i<>j时，Dij=Dji<>0；若i是k的祖先，k是j的祖先则Dij=Dik+Dkj；若k是i和j的所有公共祖先中最高级的，则Dij=Dik+Dkj。因此，利用“差异程度”，就可以确定生物进化的过程。

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

第一行是一个整数n（1<=n<=100），表示化石种类数。接下来n行，每行n个整数，第i行第j个是Dij（0<=Dij<=100000），表示i和j的“差异程度”。

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

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

 1
    1
    3