B'Polycarp has decided to decorate his room because the New Year is soon. One of the main decorations that Polycarp will install is the garland he is going to solder himself. Simple garlands consisting of several lamps connected by one wire are too boring for Polycarp. He is going to solder a garland consisting of n lamps and n - 1 wires. Exactly one lamp will be connected to power grid, and power will be transmitted from it to other lamps by the wires. Each wire connectes exactly two lamps; one lamp is called the main lamp for this wire (the one that gets power from some other wire and transmits it to this wire), the other one is called the auxiliary lamp (the one that gets power from this wire). Obviously, each lamp has at most one wire that brings power to it (and this lamp is the auxiliary lamp for this wire, and the main lamp for all other wires connected directly to it). Each lamp has a brightness value associated with it, the i -th lamp has brightness 2^i . We define the importance of the wire as the sum of brightness values over all lamps that become disconnected from the grid if the wire is cut (and all other wires are still working). Polycarp has drawn the scheme of the garland he wants to make (the scheme depicts all n lamp and n - 1 wires, and the lamp that will be connected directly to the grid is marked; the wires are placed in such a way that the power can be transmitted to each lamp). After that, Polycarp calculated the importance of each wire, enumerated them from 1 to n - 1 in descending order of their importance, and then wrote the index of the main lamp for each wire (in the order from the first wire to the last one). The following day Polycarp bought all required components of the garland and decided to solder it -- but he could not find the scheme. Fortunately, Polycarp found the list of indices of main lamps for all wires. Can you help him restore the original scheme? The first line contai'...