W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
A graph is a pair , where is a finite set of elements called vertices of the graph, and is a subset of the set of all unordered pairs of distinct vertices. The elements of the set are called edges of the graph. If for each pair of distinct vertices , there exists exactly one sequence of distinct vertices , such that , and the pairs for , then the graph is called a tree. We say that the distance between the vertices and in the tree is .
It is known that a tree of vertices has exactly edges. A tree whose vertices are numbered from to can be unambiguously described by giving the number of its vertices , and an appropriate sequence of pairs of positive integers describing its edges.
Any permutation of vertices - i.e. a sequence in which each vertex appears exactly once - is called a traversing order of a tree. If the distance of each two consecutive vertices in some order of the tree is at most , then we say that it is a traversing order of the tree with step .
It is known that for each tree its traversing order with step can be found.
The 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.
Write a program that:
In the successive lines of the standard output 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.
For the input data:
7 1 2 2 3 2 4 4 5 5 6 1 7
the correct result is:
7 2 3 5 6 4 1
Task author: Krzysztof Diks.