import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as VU
import qualified Data.IntSet as IS
import Data.Tuple (swap)
import Data.Function (on)
import Data.List (sortBy)

main :: IO ()
main = do
  n <- unsafeTextToInt <$> T.getLine :: IO Int
  as <- map unsafeTextToInt . T.words <$> T.getLine :: IO [Int]
  let
    as' = VU.fromList as :: VU.Vector Int
    f :: Tree Int -> V.Vector Int
    f = (V.replicate n 0 V.//) . flatten . pure . f' (0, IS.empty)
      where
        f' :: (Int, IS.IntSet) -> Tree Int -> Tree (Int, Int)
        f' (l, s) (Node i ts) = Node (i, l') (map (f' (l', s')) ts)
          where
            x = as' VU.! i :: Int
            (l', s') = fmap (IS.insert x) . maybe (succ l, s) ((,) l . flip IS.delete s) $ IS.lookupGE x s
  uvs <- sequence . replicate (pred n) $ unsafeListToPair . map (pred . unsafeTextToInt) . T.words <$> T.getLine :: IO [(Int, Int)]
  let
    tree = makeTree n uvs :: Tree Int
  V.mapM_ print . f $ tree

data Tree a = Node a [Tree a]

makeTree :: Int -> [(Int, Int)] -> Tree Int
makeTree n uvs = Node 0 . map (makeTree' 0) $ t V.! 0
  where
    t = V.accum (flip (:)) (V.replicate n []) . ((++) <$> id <*> map swap) $ uvs :: V.Vector [Int]
    makeTree' :: Int -> Int -> Tree Int
    makeTree' i j = Node j (map (makeTree' j) (filter (/= i) $ t V.! j))

flatten :: [Tree a] -> [a]
flatten (Node x ts : tss) = x : flatten (ts ++ tss)
flatten _                 = []

unsafeListToPair :: [Int] -> (Int, Int)
unsafeListToPair [x, y] = (x, y)

unsafeTextToInt :: T.Text -> Int
unsafeTextToInt s = case T.signed T.decimal s of
  Right (n, _) -> n
