Christmas Tree

Santa has a Christmas tree. Here a Christmas tree is a tree with $N$ nodes, and every node carries one colour. At the start every node has colour 0.

One night an elf decided the tree was boring and repainted it with $M$ updates performed one after another. On update number $X$ the elf opens gift number $X$ (someone else's gift, of course) and finds a triplet $(C, A, B)$ inside. He then paints colour $C$ on every node of the chain that joins node $A$ and node $B$. Every gift holds a different colour, so the $M$ colours are the $M$ distinct values from 1 to $M$. A node that is already painted is simply repainted, and its old colour is gone forever.

The triplets are lost. All that is left is the final tree: you are given the colour of every node after all $M$ updates. Reconstruct $M$ triplets, in order, that turn the blank tree into the given one.

The first line contains $N$ and $M$.

The second line contains $N$ integers between 1 and $M$. The $X$-th of them is the colour of node $X$.

Each of the next $N - 1$ lines contains two integers $A$ and $B$, meaning that node $A$ and node $B$ are joined by an edge.

The input satisfies the following constraints.

• $1 \le N, M \le 100000$
• every colour of the final tree is between 1 and $M$
• at least one sequence of gifts produces the given tree
• after all $M$ updates every node has been painted at least once

Print $M$ lines. Line $X$ holds the triplet $(C, A, B)$ of gift number $X$. The elf paints in the order you print, so the order matters.

Many sequences of gifts can produce the same tree, so print the one that the rules below single out.

• If colour $C$ appears in the final tree, let $P_C$ be the shortest chain that contains every node of colour $C$. The input guarantee means this chain exists, and the shortest one is unique. Print colour $C$ as C a b, where $a$ is the smaller and $b$ is the larger of the two ends of $P_C$. When $P_C$ is a single node, $a$ and $b$ are both that node.
• If colour $C$ does not appear in the final tree, print it as C 1 1.
• The colours that do not appear come first, in increasing order of colour number.
• The colours that appear come after them. Colour $C$ has to be printed before colour $D$ whenever a node of colour $D$ lies on $P_C$. Among all orders that satisfy this condition, print the one whose sequence of colour numbers is lexicographically smallest.