圣诞树（Christmas Tree）是一棵拥有 $N$ 个节点的树，每个节点都有一个颜色。最初，所有节点的颜色均为 $0$。一天晚上，一位精灵（我们称之为 Elf）因为觉得树太单调，决定对其进行涂色。在给定的树上进行了 $M$ 次连续的更新：在第 $X$ 次更新时，Elf 打开了第 $X$ 个礼物（当然，那是别人的礼物），并从中发现了一个三元组 $(C, A, B)$。随后，他将连接顶点 $A$ 和 $B$ 的路径上的所有节点涂成颜色 $C$。不同礼物中的颜色各不相同，因此我们可以假设这 $M$ 种颜色是 $1$ 到 $M$ 之间的 $M$ 个不同值。在执行第 $X$ 次更新时，某些节点可能已经被涂过色，在这种情况下，它们将被重新涂上新颜色（旧颜色将永远丢失 :( ）。

遗憾的是，我们不知道这 $M$ 次操作（礼物中的三元组），但我们知道树最终的样子（给出了执行完所有更新后每个节点的颜色）。你的任务是为树的最终生成形态找到一个可能的解决方案。更准确地说，你需要找到 $M$ 个三元组（按正确顺序），使得如果 Elf 在礼物中发现了它们，他就能得到输入中描述的圣诞树。由于可能存在多种解决方案，你可以输出其中任意一个。

数据范围

• $1 \le N, M \le 100\,000$
• 圣诞树包含的颜色索引在 $1$ 到 $M$ 之间
• 保证至少存在一个解
• 在所有 $M$ 次操作后，所有节点至少被涂色过一次

输入格式

• 第一行：$N, M$
• 第二行：$N$ 个介于 $1$ 和 $M$ 之间的整数。第 $X$ 个值表示编号为 $X$ 的顶点的颜色
• 接下来的 $N - 1$ 行描述树的边。每一行包含一对数字 $(A, B)$，表示节点 $A$ 和节点 $B$ 之间有一条边

输出格式

• $M$ 行。第 $X$ 行应包含一个三元组 $(C, A, B)$，表示 Elf 发现的第 $X$ 个礼物。警告：Elf 会按照你输出的顺序执行涂色，因此顺序非常重要。

样例

样例输入 1

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

样例输出 1

2 6 3
1 5 1
3 2 2

样例输入 2

5 3
3 2 1 2 1
1 2
1 3
1 4
4 5

样例输出 2

1 3 5
2 2 4
3 1 1