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

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

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

Constraints

Examples