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
注意
为了适合页面,示例中的几行连续行被合并为一行。实际输入遵循输入描述。