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 back into a grid. Output the points in the grid from top to bottom, left to right.

Input: Integer n,m, then n*m-1 lines which 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