Expedition Relay Camp Duplication

A mountaineering expedition maintains a branching network of camps: one base camp at the root, and every other camp is supplied by exactly one camp above it, so the whole layout forms a tree. Each camp carries a numeric camp code used for its radio call sign. Before the climb, the expedition's logistics team must build a completely independent backup network with the exact same shape and the exact same camp codes, so that if the primary network's records are ever lost the backup can still be read out on its own. You are given the primary camp network; build the backup network from scratch (brand-new camp records, not references into the primary network) and report its layout by listing the camp codes of the backup network in pre-order: visit a camp, then recursively visit its supply camps from first to last, in exactly the order they were listed for the primary network.

Input format

• Line 1: an integer n — the number of camps (1 <= n <= 10^4). Camps are numbered 1 to n, and camp 1 is always the base camp (the root).
• Line 2: n integers — the camp code of camp 1, camp 2, ..., camp n, in order (each code satisfies -10^9 <= code <= 10^9).
• The next n - 1 lines each contain two integers p c, meaning camp c is directly supplied by camp p (camp c is a child of camp p). Among all lines naming the same parent p, the order those lines appear in the input is the left-to-right order of p's supply camps. The given edges are guaranteed to form a valid tree rooted at camp 1 (every camp other than camp 1 has exactly one parent, and there are no cycles).

Output format

Print n integers separated by single spaces on one line: the camp codes of the backup network visited in pre-order, starting from the backup of camp 1 and recursing into its supply camps in the same left-to-right order given in the input.

Constraints

• 1 <= n <= 10^4
• -10^9 <= camp code <= 10^9
• The given n - 1 edges always form a valid tree rooted at camp 1.

4
1 2 3 4
1 2
1 3
3 4

1 2 3 4

1
7

7