A strange problem

Revision en3, by mutsuki, 2022-06-03 18:52:55

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

Tags tree, problem solving

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English mutsuki 2022-06-03 19:15:28 7 Tiny change: 'e turn it into grid. Out' -> 'e turn it back into a grid. Out' (published)
en7 English mutsuki 2022-06-03 19:13:33 199 Tiny change: ':\n\no o o\no o o\n\' -> ':\n\no o o \no o o\n\'
en6 English mutsuki 2022-06-03 18:55:57 340
en5 English mutsuki 2022-06-03 18:54:46 355
en4 English mutsuki 2022-06-03 18:54:01 56
en3 English mutsuki 2022-06-03 18:52:55 64
en2 English mutsuki 2022-06-03 18:51:49 347
en1 English mutsuki 2022-06-03 18:51:00 1702 Initial revision (saved to drafts)