← 返回题目列表

Codeforces · 1773/B

B. 币币

中文机器翻译题面 查看原题

BinCoin 公司有 $$$n$$$ 员工,编号从 $$$1$$$ 到 $$$n$$$。该公司的隶属结构是一棵有根的树。换句话说:

  • 公司有一位首席执行官——主要老板。
  • 每名其他员工都有一位直接上级。
  • 从属结构中没有循环。

而且,由于 BinCoin 的 CEO 对所有二进制东西有着莫名的喜爱,公司内部的隶属结构是 二进制 有根树。这意味着每个员工都直接优于零或两名其他员工。

在首席执行官看来,在这家公司工作几乎和在矿山一样危险。因此,员工有时应该签署索赔弃权书。此过程按以下方式发生。最初,CEO 获取日志,然后递归执行以下过程:

  • 如果持有日记帐的员工没有任何下属,他们会在日记帐中签署弃权书并将其返还给其上级。如果是没有上级的首席执行官,程序就会停止。
  • 否则
    • 他们统一随机选择两名直属下属之一,并将日志交给其中一名;
    • 当他们拿回日志时,他们会在上面签名;
    • 然后他们把它交给另一个直属下属;
    • 当他们再次取回它时,他们将其返还给他们的上级。如果是没有上级的首席执行官,程序就会停止。

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

有一天,首席执行官意识到他们不记得从属树了。幸运的是,他们的日记本上有 $$$k$$$ 记录。每条记录都是员工的序列,按照他们在日记中签名的顺序排列。

帮助CEO恢复从属树。

输入

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

接下来的 $$$k$$$ 行中的每一行都包含从 $$$1$$$ 到 $$$n$$$ 的整数排列 - 相应记录中员工的顺序。

保证输入是按照声明中描述的方式通过真正的随机选择获得的。

输出

输出$$$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 

注意

为了适合页面,示例中的几行连续行被合并为一行。实际输入遵循输入描述。