I came up with a strange problem and find it hard for me to solve it, so i write this topic to ask for help.

Consider a point grid, for example, a 2x3 point grid may looks like this:

o o o o o o

Now we connect each pair of adjacent points.

o--o--o | | | o--o--o

As we have some points and edges, it now becomes a graph! Now we are gonna find one of its spanning tree. Like this one:

o--o--o | | o o--o

We can see that this tree is a 'rectangle'. Trees obtained by this way is called a rect-tree. Now, consider this rect-tree: n=6 1 6 1 2 2 3 2 4 4 5

We can turn it back into a grid. Like this:

1 2 3 o--o--o | | o o--o 6 4 5

The problem is here:

Give you a rect-tree, please turn it into grid. Output the points in the grid from top to bottom, left to right.

Input: Integer n,m Then n*m-1 lines describes the tree.

Output: n*m numbers.

Case 1: Input 2 3

1 6 1 2 2 3 2 4 4 5

Output: 1 2 3 6 4 5

At first, i thought this problem was a piece of cake and can be easily solved with 2 < n,m < 5000. However, now I find it hard to solve even when 2< n,m < 5. Can anyone help me?

By the way, here are some more testcases.

Input: 3 3

1 2 1 3 1 4 4 5 4 6 5 7 4 8 6 9

Output: 2 1 3 5 4 6 7 8 9

It looks like this o--o--o | o--o--o | | | o o o