[R32D]还原树 - 代码源竞赛平台

时空限制

1S/512M

题目描述

apiadu 曾经拥有一棵包含 $n$ 个节点的有根树，节点编号为 $1$ 到 $n$。然而，这棵树的原始父子关系现在已经丢失。

幸运的是，apiadu 还保留着一个完整的 $n \times n$ 矩阵 $L$，其中 $L_{i ,j }$ 记录了原始树中节点 $i$ 与节点 $j$ 的最近公共祖先 (LCA)。

已知对于任意两个节点 $u$ 和 $v$，它们的最近公共祖先 $w$ 满足：

• $w$ 是 $u$ 和 $v$ 的共同祖先；

• 在所有共同祖先中，$w$ 的深度最大。

注意：每个节点也是其自身的祖先。

请你帮助 apiadu 根据这个矩阵，输出原来的有根树的每个节点的父亲，其中根节点的父亲设为 $-1$。保证树存在。

格式

输入格式

输入的第一行包含一个整数 $n$，表示树的节点数量。

接下来 $n$ 行，每行包含 $n$ 个整数。其中第 $i$ 行第 $j$ 列的数表示 $L_{i,j}$。

输出格式

输出一行，包含 $N$ 个用空格隔开的整数 $p_1, p_2, \ldots, p_n$，其中 $p_i$ 表示节点 $i$ 的父节点（根节点的父亲为 $-1$）。

样例

样例输入 #1

4
1 1 1 1
1 2 1 2
1 1 3 1
1 2 1 4

样例输出 #1

-1 1 1 2

样例解释 #1

样例表示的树如下：

数据规模

对于 $30\%$ 的数据，$1 \leq n \leq 5$。

对于 $100\%$ 的数据，$1 \leq n \leq 1000$。保证输入的矩阵是合法的，并且能够唯一确定一棵有根树的结构。