Description

在 BinCoin 公司有 $n$ 名员工，编号从 $1$ 到 $n$。这家公司的隶属关系结构是一棵有根树。换句话说：

• 公司中有一位 CEO——即最高领导。
• 其他每位员工都恰好有一位直接上级。
• 隶属关系结构中没有环。

此外，由于 BinCoin 的 CEO 对所有二进制的东西有着莫名的喜爱，公司的隶属关系结构是一棵二叉有根树。这意味着每位员工要么是零位、要么是两位其他员工的直接上级。

在 CEO 看来，在这家公司工作几乎和在矿山里一样危险。因此，员工们有时需要签署免责声明。这个过程按以下方式进行。首先，CEO 拿起记录本，然后递归地执行以下流程：

• 如果持有记录本的员工没有任何下属，他们会在记录本上签名，然后将其交还给他们的上级。如果该员工是 CEO（他没有上级），则流程结束。
• 否则
  • 他们从两名直接下属中随机均匀地选择一位，并将记录本交给他；
  • 当他们收回记录本时，他们自己签名；
  • 然后他们将记录本交给另一位直接下属；
  • 当他们再次收回记录本时，他们将其交还给他们的上级。如果该员工是 CEO（他没有上级），则流程结束。

所有的随机选择都是独立的。

一天，CEO 发现他们记不起隶属关系树了。幸运的是，他们有那个记录本，上面有 $k$ 条记录。每条记录都是一个员工序列，表示他们在记录本上签名的顺序。

请帮助 CEO 恢复这棵隶属关系树。

Input Format

第一行包含两个整数 $n$ 和 $k$——员工数量和记录本中的记录数量 ($1 \le n \le 999$; $50 \le k \le 100$)。

接下来的 $k$ 行，每行包含一个从 $1$ 到 $n$ 的整数排列——表示相应记录中员工的签名顺序。

保证输入数据是在所述的真实随机选择下生成的。

Output Format

输出 $n$ 个整数 $p_i$。如果员工 $i$ 是 CEO，那么 $p_i$ 应为 $-1$。否则，$p_i$ 应为员工 $i$ 的直接上级的编号。

你的输出应对应一棵二叉有根树。如果有多棵树满足输入条件，你可以输出任意一棵。

3 50
1 2 3    1 2 3    3 2 1    1 2 3
3 2 1    1 2 3    1 2 3    1 2 3
1 2 3    3 2 1    1 2 3    3 2 1
1 2 3    3 2 1    1 2 3    3 2 1
1 2 3    1 2 3    3 2 1    1 2 3
3 2 1    1 2 3    3 2 1    1 2 3
1 2 3    3 2 1    1 2 3    1 2 3
1 2 3    1 2 3    3 2 1    1 2 3
3 2 1    3 2 1    1 2 3    3 2 1
1 2 3    3 2 1    3 2 1    1 2 3
1 2 3    3 2 1    1 2 3    3 2 1
3 2 1    3 2 1    1 2 3    1 2 3
3 2 1    3 2 1    

2 -1 2

5 60
2 4 3 5 1    1 5 2 4 3    1 5 2 4 3
1 5 2 4 3    1 5 3 4 2    1 5 3 4 2
1 5 3 4 2    1 5 3 4 2    1 5 3 4 2
3 4 2 5 1    2 4 3 5 1    1 5 2 4 3
3 4 2 5 1    2 4 3 5 1    2 4 3 5 1
1 5 2 4 3    3 4 2 5 1    3 4 2 5 1
1 5 2 4 3    2 4 3 5 1    1 5 2 4 3
1 5 3 4 2    3 4 2 5 1    1 5 3 4 2
1 5 2 4 3    1 5 3 4 2    1 5 2 4 3
2 4 3 5 1    2 4 3 5 1    2 4 3 5 1
2 4 3 5 1    2 4 3 5 1    1 5 2 4 3
1 5 3 4 2    1 5 2 4 3    3 4 2 5 1
1 5 3 4 2    3 4 2 5 1    3 4 2 5 1
1 5 2 4 3    2 4 3 5 1    1 5 2 4 3
1 5 3 4 2    2 4 3 5 1    2 4 3 5 1
1 5 2 4 3    1 5 2 4 3    1 5 2 4 3
1 5 2 4 3    1 5 2 4 3    3 4 2 5 1
3 4 2 5 1    3 4 2 5 1    1 5 2 4 3
1 5 3 4 2    1 5 3 4 2    2 4 3 5 1
3 4 2 5 1    1 5 2 4 3    3 4 2 5 1

5 4 4 5 -1

Hint

为了适应页面大小，样例中的几行连续的输入被合并到了一行。真实的输入遵循输入格式描述。

翻译由 gemini2.5pro 完成