Dano je binarno stablo od \(n\) čvorova s korijenom \(1\) i u svakom čvoru se nalazi neki broj \(x_i\). Rotacija čvora je operacija kojom zamjenimo lijevo i desno dijete tog čvora. Ako ne postoji lijevo dijete, onda samo premjestiom desno dijete na lijevu stranu. Isto vrijedi i ako nema desnog djeteta. Inorder ispis stabla je kada prvo ispišemo lijevo podstablo čvora, zatim ispišemo broj koji se nalazi u trenutnom čvoru i na kraju ispišemo desno podstablo trenutnog čvora. Vaš zadatak je naći stablo sa leksikografski najmanjim inorder obilaskom koje možete dobiti koristeći samo operaciju rotacije navedenu gore.

Ulaz

U prvom retku se nalazi broj \(n\), \((1 \leq n \leq 2 \cdot 10^5)\), broj čvorova u stablu. U sljedećem retku se nalazi \(n\) brojeva \(x_i\), \((1 \leq x_i \leq 10^9)\), broj koji se nalazi u \(i\)-tom čvoru. Zatim u sljedećih \(n-1\) redaka dana su po dva broja, \(u_i\) i \(v_i\), čvorovi \(u_i\) i \(v_i\) su povezani bridom. U zadatku će uvijek biti dano valjano binarno stablo s korijenom 1.

Izlaz

U jednom retku ispišite \(n\) brojeva, leksikografski minimalan inorder ispis binarnog stabla koje se može dobiti koristeći samo operaciju rotacije. U \(50%\) testnih primjera će svi brojevi biti različiti.

Ulaz primjera

5
8 1 4 2 6
1 2
5 1
5 4
3 5

Izlaz primjera

1 8 2 6 4

Ulaz primjera

10
1 2 3 4 5 6 7 8 9 10
1 2
2 3
3 4
4 5
4 6
6 7
7 8
8 9
3 10

Izlaz primjera

1 2 5 4 6 7 8 9 3 10

Ulaz primjera`

7
2 2 2 1 3 1 1
1 2
1 3
2 4
2 5
3 6
3 7

Izlaz primjera

1 2 1 2 1 2 3