Distance Code

Time limit1sMemory limit1024 MB

Summary

Write an encoder that orders the removal of tree leaves, and a decoder that rebuilds an isomorphic tree from the distances between successive removed nodes.

Level: Hard8 of 10
Topics: Tree, Implementation, BFS
Solved: No attempts yet

Problem

Your task is to create a program that can be used in two ways: as an encoder and as a decoder.

The encoder is given a tree of $n$ nodes and removes all nodes from the tree. On each step, the encoder may remove any leaf from the current tree.

The decoder is given a list of distances between successively removed nodes by the encoder. It has to reconstruct the original structure of the tree. The decoder has to create a tree with the same structure as the original tree (more precisely, it has to be isomorphic to the original tree).

Input

The first line has an integer $t$ , which is either $1$ (encoder) or $2$ (decoder).

The second line has an integer $n$ , the number of nodes in the tree. The nodes are numbered $1,2,\dots,n$ .

If $t=1$ , there are then $n-1$ lines describing the tree. Each line has two integers $a$ and $b$ , meaning there is an edge between nodes $a$ and $b$ .

If $t=2$ , there is only one line with $n-1$ integers: the distances between successively removed nodes.

Output

If $t=1$ , the encoder has to print a permutation of the numbers $1,2,\dots,n$ : the order in which the nodes are removed from the tree.

If $t=2$ , the decoder has to print $n-1$ lines that describe the structure of the tree.

Examples2

Example 1
Input
```
1
3
1 2
2 3
```
Expected output
```
1 3 2
```
Example 2
Input
```
2
3
2 1
```
Expected output
```
2 3
1 3
```