15395번 - Christmas Tree 다국어

Santa has a Christmas Tree. In computer science terms, a Christmas Tree is a tree with N nodes where each node has a colour. Initially, all nodes have colour 0. One night, an elf comes (we call him Elf) to paint the tree because he found it very boring. M consecutive updates were performed on the given tree the following way: on update number X, Elf opens gift number X before Christmas (of course, it’s someone else’s gift) and finds a triplet (C, A, B) in it. After that, he paints with colour C all the nodes which can be found on the chain formed by vertices A and B. All colours are different from gift to gift, so we can assume that the M colours are M distinct values from 1 to M. While performing update X, some nodes may already be painted, in which case they will just be repainted with the new colour (the old one is lost forever :( )

Unfortunately, we do not know the M operations (the triplets found in the gifts), but we do know how the tree looks like in the end (you are given the colour of each node after performing all updates). Your task is to find a possible solution for the generated final form of the tree. More precisely, you have to find M triplets (in the correct order), such that if Elf would have found them in the gifts, he would obtain the Christmas Tree described in the input. Since there can be multiple solutions, you can display any of them.

• First line: N, M
• Second Line: N integers between 1 and M. The X-th value denotes the colour of the vertex number X
• The next N - 1 lines describe the edges of the tree. Each such line contains a pair of numbers (A, B), meaning that there is an edge between node A and node B

Constraints

• 1 ≤ N, M ≤ 100.000
• The Christmas Tree will contain colours with indexes between 1 and M
• It is guaranteed that there always exists at least one solution
• After all M operations all nodes will have been painted at least once 

• M lines. Line number X should contain a triplet (C, A, B), denoting the X-th gift found by Elf. Warning: Elf performs the drawings in the order of your output, so order DOES matter.