The country of Foostonia is in turmoil. Civil war rages through the
land, and armies sprout up overnight to fight one another before
dissolving and reforming again. National intelligence would like to
track these armies, and most importantly determine the chain of
command (if any). Satellite reconnaissance of battles in progress
have been processed, providing information for each unit of each army
at one hour intervals: is the unit advancing or retreating?
As it turns out, this information should be sufficient to determine
the hierarchy. Every unit, in the absence of orders from its
superiors, will do whatever it likes (and inform its subordinates to
do the same). Upon receiving orders, all units will follow them
perfectly. It takes exactly one hour for orders to be sent down each
link in the chain of command.
Here is an example. Each row is the information for a single hour,
each column is the information for a single unit. A "1" indicates
attacking, a "0" indicates retreating.
010 101 000
In this example, we can clearly see that units #1 (the left column) and #3 (the right column) track the actions of unit #2, with the appropriate 1-hour delay. Thus in this instance, unit #2 is the commander of both. Hierarchically this can be represented as:
2 1 3
Input: Input will be a series of lines, one per hour,
representing the advance/retreat behavior of the units.
Output: You will output the chain of command as follows: For a
commanding unit at depth n (the topmost unit is level 0), print
n spaces followed by the unit number. Then recursively print
the subordinate units, in sorted order.
If a unit could be subordinate to more than one unit, assume it is
subordinate to the unit with the smaller number.
Sample Input/Output
armies1.in armies1.out
armies2.in armies2.out