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
