Job Lookup

Julia's $n$ friends want to organize a startup in a new country they moved to. They assigned each other numbers from 1 to $n$ according to the jobs they have, from the most front-end tasks to the most back-end ones. They also estimated a matrix $c$, where $c\_{ij} = c\_{ji}$ is the average number of messages per month between people doing jobs $i$ and $j$.

Now they want to make a hierarchy tree. It will be a binary tree with each node containing one member of the team. Some member will be selected as a leader of the team and will be contained in the root node. In order for the leader to be able to easily reach any subordinate, for each node $v$ of the tree, the following should apply: all members in its left subtree must have smaller numbers than $v$, and all members in its right subtree must have larger numbers than $v$.

After the hierarchy tree is settled, people doing jobs $i$ and $j$ will be communicating via the shortest path in the tree between their nodes. Let's denote the length of this path as $d\_{ij}$. Thus, the cost of their communication is $c\_{ij} \cdot d\_{ij}$.

Your task is to find a hierarchy tree that minimizes the total cost of communication over all pairs: $\sum\_{1 \le i < j \le n} c\_{ij} \cdot d\_{ij}$.

The first line contains an integer $n$ ($1 \le n \le 200$) -- the number of team members organizing a startup.

The next $n$ lines contain $n$ integers each, $j$-th number in $i$-th line is $c\_{ij}$ --- the estimated number of messages per month between team members $i$ and $j$ ($0 \le c\_{ij} \le 10^9; c\_{ij} = c\_{ji}; c\_{ii} = 0$).

Output a description of a hierarchy tree that minimizes the total cost of communication. To do so, for each team member from 1 to $n$ output the number of the member in its parent node, or 0 for the leader. If there are many optimal trees, output a description of any one of them.

The minimal possible total cost is $566 \cdot 1+239 \cdot 1+30 \cdot 1+1 \cdot 2+1 \cdot 2=839$: