2022-2023 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred) |
---|
Finished |
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:
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:
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.
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
In order to fit on the page, several consecutive lines in the examples were joined into one. The real inputs follow the input description.
Name |
---|