### Problem Statement

The city of Konigsberg is famous for its bridges. The Tour de Konigsberg is an annual bicycle race over a route that crosses each bridge exactly once. You are responsible for planning the route for this year's race.

A series of checkpoints numbered from 0 to N-1 have been set up around the city, with exactly one bridge between each pair of neighboring checkpoints. For example, here is a picture of the bridges and checkpoints from last year's race.

```    0-------1
|       |
|       |
|       |
2-------3
|\     /|
| \   / |
|  \ /  |
4---5---6
```
(There has been substantial construction since last year, however, so the bridges and checkpoints for this year's race may be completely different.)

The route for the race must begin and end at checkpoint 0, and must proceed across the bridges from checkpoint to checkpoint, crossing each bridge exactly once. If the checkpoints are placed poorly, it might not be possible to come up with such a route, so the planner for the first Tour de Kongisberg, Leonhard Euler, was careful to leave instructions for how to lay out the checkpoints to guarantee that a successful race route will be possible. He decreed that the checkpoints should be placed with an even number of bridges (greater than zero) leaving each checkpoint, and furthermore that every checkpoint must be reachable from checkpoint 0. The checkpoints for this year's race were placed with Euler's instructions in mind. Now your task is to plan the race route. Fortunately, Euler also left notes telling you how.

You begin by laying out a tentative route that begins and ends at checkpoint 0. At every step along the way, this initial route leaves the current checkpoint via the unused bridge that leads to the lowest numbered checkpoint. When the tentative route returns to checkpoint 0, it may or may not have used all the bridges. If it has, you are done. Otherwise, you need to extend the route to use more bridges as follows. Beginning at checkpoint 0, you follow the tentative route until you reach a checkpoint--call it checkpoint K--that has an unused bridge leading out from it. (Note that K could be 0.) Lay out a new route by starting at checkpoint K and repeatedly taking the unused bridge that leads to the lowest numbered checkpoint until you return to checkpoint K. Now splice this new route into the tentative route after the first occurrence of K. Repeat this extension process on the new larger tentative route until all the bridges have been used. Note that you always restart the search for a checkpoint with an unused bridge back at the beginning of the tentative route; you do not continue from where you left off.

For example, in last year's race, the initial tentative route travelled from checkpoint 0 to 1 to 3 to 2. Marking the used bridges with x's we get

```    0-x-x-x-1
|       |
x       x
|       |
2-x-x-x-3
|\     /|
| \   / |
|  \ /  |
4---5---6
```
Some bridges have not been used, so we retrace the tentative route until we reach checkpoint 3. Then we lay out a new route from checkpoint 3 to 5 to 2 to 4 to 5 to 6 to 3. Splicing this new route back into the original route, we end up with the final race route: 0-1-3-5-2-4-5-6-3-2-0.

You will be given a String[] bridges that contains information about which checkpoints are connected by bridges. The i-th character of element j of bridges is '1' if there is a bridge between checkpoints i and j. Otherwise, it is '0'. Note that both i and j are zero based. All bridges are two-way so a bridge between checkpoints i and j appears in bridges in both directions, from i to j and from j to i. You will return a int[] containing the sequence of checkpoints visited by the race route.

### Definition

 Class: EulerianRace Method: planRoute Parameters: String[] Returns: int[] Method signature: int[] planRoute(String[] bridges) (be sure your method is public)

### Constraints

-bridges contains between 3 and 30 elements, inclusive.
-Every element of bridges contains the same number of characters as elements in bridges.
-Every element in bridges contains only the characters '0' and/or '1'.
-Every element in bridges contains a positive even number of '1's.
-Character i of element i of bridges is '0'.
-Character i of element j of bridges is equal to character j of element i of bridges.
-Every checkpoint is reachable from checkpoint 0.

### Examples

0)

 ```{ "0110000", "1001000", "1001110", "0110011", "0010010", "0011101", "0001010" }```
`Returns: { 0,  1,  3,  5,  2,  4,  5,  6,  3,  2,  0 }`
 The example from last year's race.
1)

 ```{ "0101000000", "1010110000", "0101000000", "1010000011", "0100011100", "0100100000", "0000100100", "0000101000", "0001000001", "0001000010" }```
`Returns: { 0,  1,  4,  6,  7,  4,  5,  1,  2,  3,  8,  9,  3,  0 }`
 In this example, the bridges and checkpoints are arranged as follows: ``` 0-------1---4---6 | |\ |\ | | | \ | \ | | | \| \| 3-------2 5 7 |\ | \ | \ 8---9 ``` The initial tentative route is 0-1-2-3-0, which is then extended with 1-4-5-1 into 0-1-4-5-1-2-3-0. Next, it is extended with 4-6-7-4 into 0-1-4-6-7-4-5-1-2-3-0. Finally, it is extended with 3-8-9-0 into 0-1-4-6-7-4-5-1-2-3-8-9-3-0.
2)

 ```{ "01111", "10111", "11011", "11101", "11110" }```
`Returns: { 0,  3,  2,  4,  3,  1,  4,  0,  1,  2,  0 }`
 A bridge between every possible pair of checkpoints.
3)

 ```{ "01000000001", "10100000000", "01010000000", "00101000000", "00010100000", "00001010000", "00000101000", "00000010100", "00000001010", "00000000101", "10000000010" }```
`Returns: { 0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  10,  0 }`
 The bridges and checkpoints are arranged in a big circle.
4)

 ```{ "00011", "00101", "01001", "10001", "11110" }```
`Returns: { 0,  3,  4,  1,  2,  4,  0 }`
5)

 ```{"011111111", "101000000", "110000000", "100010000", "100100000", "100000100", "100001000", "100000001", "100000010"}```
`Returns: { 0,  7,  8,  0,  5,  6,  0,  3,  4,  0,  1,  2,  0 }`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2373

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4745&pm=2373

vorthys

#### Testers:

lbackstrom , brett1479

#### Problem categories:

Graph Theory, Simulation