크리스마스 트리

산타에게 크리스마스 트리가 있다. 여기서 크리스마스 트리는 노드가 $N$개인 트리이고, 각 노드에는 색이 하나씩 칠해져 있다. 처음에는 모든 노드의 색이 0이다.

어느 날 밤, 요정 하나가 트리가 밋밋하다고 생각해 $M$번의 갱신으로 트리를 새로 칠했다. $X$번째 갱신에서 요정은 $X$번 선물을 (물론 남의 선물이다) 열어 그 안에서 삼중항 $(C, A, B)$를 찾는다. 그리고 노드 $A$와 노드 $B$를 잇는 경로 위의 모든 노드를 색 $C$로 칠한다. 선물마다 색이 다르므로 $M$개의 색은 1부터 $M$까지의 서로 다른 값이다. 이미 칠해진 노드는 새 색으로 덮여 칠해지고, 이전 색은 영영 사라진다.

삼중항은 남아 있지 않다. 남은 것은 마지막 트리뿐이어서, $M$번의 갱신이 모두 끝난 뒤의 각 노드 색만 주어진다. 빈 트리를 주어진 트리로 만드는 삼중항 $M$개를 순서대로 복원하라.

첫째 줄에 $N$과 $M$이 주어진다.

둘째 줄에 1 이상 $M$ 이하의 정수 $N$개가 주어진다. 그중 $X$번째 값은 노드 $X$의 색이다.

다음 $N - 1$개의 줄에는 두 정수 $A$와 $B$가 주어지며, 노드 $A$와 노드 $B$가 간선으로 이어져 있다는 뜻이다.

입력은 다음 제한을 만족한다.

• $1 \le N, M \le 100000$
• 마지막 트리에 나타나는 색은 모두 1 이상 $M$ 이하이다
• 주어진 트리를 만드는 선물 순서가 적어도 하나 존재한다
• $M$번의 갱신이 끝나면 모든 노드는 적어도 한 번 칠해져 있다

$M$개의 줄을 출력한다. $X$번째 줄에는 $X$번 선물에 들어 있던 삼중항 $(C, A, B)$를 출력한다. 요정은 출력한 순서대로 칠하므로 순서가 중요하다.

같은 트리를 만드는 선물 순서가 여러 가지일 수 있으므로, 아래 규칙이 정하는 하나만 출력한다.

• 마지막 트리에 색 $C$가 나타나면, 색이 $C$인 노드를 모두 포함하는 가장 짧은 경로를 $P_C$라 하자. 입력 조건에 따라 이런 경로는 존재하고, 가장 짧은 것은 유일하다. 색 $C$는 C a b 꼴로 출력하며, $a$는 $P_C$의 두 끝 노드 중 작은 쪽, $b$는 큰 쪽이다. $P_C$가 노드 하나면 $a$와 $b$ 모두 그 노드다.
• 마지막 트리에 색 $C$가 나타나지 않으면 C 1 1로 출력한다.
• 나타나지 않는 색을 먼저, 색 번호가 작은 것부터 출력한다.
• 그 뒤에 나타나는 색을 출력한다. $P_C$ 위에 색이 $D$인 노드가 있으면 색 $C$를 색 $D$보다 먼저 출력해야 한다. 이 조건을 만족하는 순서 중에서 색 번호를 나열한 수열이 사전순으로 가장 앞서는 것을 출력한다.