## Step Traversing a Tree

## POI II Stage 3 Problem 2## Step Traversing a Tree
A w_{0} = u,
w = _{k}v and the pairs
{w, _{i}w_{i + 1}}
are in E, for i = 0,
..., k - 1, then the graph is called a tree. We
say that the distance between the vertices u and v in the
tree is k.
It is known that a tree of
Any permutation of vertices - i.e. a sequence in which each vertex
appears exactly once - is called a It is known that for each tree its traversing order with step 3 can be found. ## ExampleThe picture shows a tree of 7 vertices. The vertices are represented by black dots, and edges by line segments joining the dots.
This tree can be traversed with step 3 by visiting its vertices in the following order: 7 2 3 5 6 4 1. ## TaskWrite a program that:- reads a description of a tree from the text file DRZ.IN,
- finds an arbitrary traversing order of that tree with step 3,
- writes that order in the text file DRZ.OUT.
## Input- In the first line of the file DRZ.IN there is a positive integer
*n*, not greater than 5000 - it is the number of vertices of the tree. - In each of the following
*n*- 1 lines there is one pair of positive integers separated by a single space and representing one edge of the tree.
## OutputIn the successive lines of the file DRZ.OUT one should write the numbers of the successive vertices in a traversing order of the tree with step 3 - each number should be written in a separate line.## ExampleThe following file DRZ.IN is a correct description of the tree presented in the picture:7 1 2 2 3 2 4 4 5 5 6 1 7The following file DRZ.OUT is a correct solution: 7 2 3 5 6 4 1SubmitStatistics |