BinCoin

题意翻译

## 题目描述 BinCoin 公司有 $n$ 个员工，编号为 $1$ 到 $n$。公司的从属结构是一棵有根树，换句话说： - 公司有一个 CEO —— 老板。 - 其他雇员都有一个直系领导。 - 结构中不存在循环。 另外，由于 CEO 对所有二进制物品的迷之喜爱，公司的结构也是一棵二叉树。也就意味着，每个雇员直接领导着其他 $0$ 或 $2$ 个雇员。 在 CEO 的认知中，在该公司工作的危险程度不亚于挖矿。因此，雇员们有时需要签署放弃索赔承诺书。签署过程如下， 首先，CEO 拿着日志，然后递归进行以下步骤： - 如果拿到日志的雇员没有下属，他们会在日志上签署自己的名字，然后将其归还给直接领导。该过程在日志传递到 CEO 时结束。 - 否则， - 该雇员会随机将日志传递给自己两个下属中的任意一个。 - 从下属手里收回日志后，他会签上自己的名字，又将其递给另一个下属， - 当再一次得到日志，就会把它交给自己的直接领导。 而所有随机选择都是独立的。 一天，CEO 忘记了职员们的从属关系结构，幸运的是，他们留有 k 条记录的日志。每条记录都是一个序列，顺序为职员们的签名顺序。 请帮助 CEO 恢复他们的从属关系。 ## 输入格式 第一行包含两个整数 $n$ 和 $k$ -- 雇员的数量和日志中的记录数量。 接下来 $k$ 行，每一行都包含一个从 $1$ 到 $n$ 的整数排列 -- 相应记录中雇员的顺序。 保证输入是按照语句中描述的真实随机选择获得的。 ## 输出格式 输出一行 $n$ 个整数 $p_i$。$p_i$ 为第 $i$ 个雇员的直接上司，如果 $i$ 为 CEO ，则输出 $-1$。 你的输出应该对应于一棵二叉树。如果有几棵树满足输入的要求，你可以输出其中任何一棵。

题目描述

There are $ n $ employees in the BinCoin company numbered from $ 1 $ to $ n $ . The subordination structure in this company is a rooted tree. In other words: - There is one CEO in the company — the main boss. - Each other employee has exactly one direct superior. - There are no cycles in the subordination structure. Moreover, due to the inexplicable love of the CEO of BinCoin for all the binary stuff, the subordination structure in the company is a binary rooted tree. That means each employee is directly superior to exactly zero or two other employees. In the CEO's opinion, working in this company is almost as dangerous as in mines. So, employees should sign the waiver of claims sometimes. This process happens in the following way. Initially, CEO takes the journal, then recursively the following procedure is performed: - If an employee that holds the journal does not have any subordinates, they sign the waiver in the journal and give it back to their superior. The procedure stops if that was the CEO, who has no superior. - Otherwise - they choose one of two of their direct subordinates uniformly at random and give the journal to one of them; - when they get the journal back, they sign it; - and then they give it to another direct subordinate; - when they get it back again, they give it back to their superior. The procedure stops if that was the CEO, who has no superior. All random choices are independent. One day, the CEO realized that they could not remember the subordination tree. Fortunately, they have the journal with $ k $ records. Each record is a sequence of employees in the order they've signed in a journal. Help CEO restore the subordination tree.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ k $ — the number of employees and the number of records in the journal ( $ 1 \le n \le 999 $ ; $ 50 \le k \le 100 $ ). Each of the next $ k $ lines contains a permutation of integers from $ 1 $ to $ n $ — the order of employees in the corresponding record. It is guaranteed that the input was obtained as described in the statement with a real random choice.

输出格式

Output $ n $ integers $ p_i $ . If $ i $ is a CEO, then $ p_i $ should be $ -1 $ . Otherwise, $ p_i $ should be the index of the direct superior of $ i $ -th employee. Your output should correspond to a binary rooted tree. If there are several trees satisfying the input, you can output any one of them.

输入输出样例

输入样例 #1

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

输出样例 #1

2 -1 2

输入样例 #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

输出样例 #2

5 4 4 5 -1

说明

In order to fit on the page, several consecutive lines in the examples were joined into one. The real inputs follow the input description.

**题目大意：**

BinCoin 公司的员工从属关系结构是一棵二叉树，每个员工直接领导0个或2个员工。员工们有时需要签署放弃索赔承诺书，签署过程是递归的，CEO开始，然后随机选择一个直接下属传递日志，下属签署后再传递给另一个下属，最后交还给上级。所有选择都是独立的。现在CEO忘记了从属关系结构，但保留了k条日志记录，每条记录是员工签名顺序的序列。需要帮助CEO恢复从属关系。

**输入输出数据格式：**

- **输入格式：**
- 第一行包含两个整数 $ n $ 和 $ k $，分别表示员工数量和日志记录数量。
- 接下来的 $ k $ 行，每行包含一个从 $ 1 $ 到 $ n $ 的整数排列，表示相应记录中员工的签名顺序。

- **输出格式：**
- 输出 $ n $ 个整数 $ p_i $。如果 $ i $ 是CEO，则 $ p_i $ 为 $ -1 $；否则 $ p_i $ 为第 $ i $ 个员工的直接上司的编号。
- 输出应对应于一棵二叉树。如果有几棵树满足输入要求，可以输出其中任何一棵。**题目大意：** BinCoin 公司的员工从属关系结构是一棵二叉树，每个员工直接领导0个或2个员工。员工们有时需要签署放弃索赔承诺书，签署过程是递归的，CEO开始，然后随机选择一个直接下属传递日志，下属签署后再传递给另一个下属，最后交还给上级。所有选择都是独立的。现在CEO忘记了从属关系结构，但保留了k条日志记录，每条记录是员工签名顺序的序列。需要帮助CEO恢复从属关系。 **输入输出数据格式：** - **输入格式：** - 第一行包含两个整数 $ n $ 和 $ k $，分别表示员工数量和日志记录数量。 - 接下来的 $ k $ 行，每行包含一个从 $ 1 $ 到 $ n $ 的整数排列，表示相应记录中员工的签名顺序。 - **输出格式：** - 输出 $ n $ 个整数 $ p_i $。如果 $ i $ 是CEO，则 $ p_i $ 为 $ -1 $；否则 $ p_i $ 为第 $ i $ 个员工的直接上司的编号。 - 输出应对应于一棵二叉树。如果有几棵树满足输入要求，可以输出其中任何一棵。