|Home||I n t e r n e t C o n t e s t||i n t e r n e t
c o n t e s t
|C E O I
2 0 0 0
Problem 2 : The Caterpillar
Definition: A caterpillar is a particular kind of tree with the following property: there is a central chain such that each of the tree's nodes lie either on the central chain, or they are adjacent to that chain. Below there are shown two caterpillars. The darkened nodes indicate the chain.
The chain is not necessarily unique. For example, another possible chain for the second caterpillar is 3-2-5-9.
Given a caterpillar with N nodes, write a program which labels the nodes with numbers from 1 to N such that:
For the second caterpillar above, a possible labeling is indicated below along with the corresponding differences on the edges:
File name: CP.IN
Line 1: N
Lines 2..N: X Y
The input data is correct, and the input tree is a caterpillar.
File name: CP.OUT
Line 1: L1 L2 ... LN
If there are multiple solutions, only one is required. If no labeling is possible, the output file should contain only one line with the word: IMPOSSIBLE
The following input (CP.IN) describes the caterpillar from the Figure 2 and the output (CP.OUT) the labeling from the Figure 3.
CP.IN CP.OUT (one possible solution) 9 8 1 5 2 9 4 6 3 7 1 2 6 5 5 7 4 2 2 3 8 5 2 5 5 9