Farmer John 的农场有 NN 个牛棚（2≤N≤2⋅1052≤N≤2⋅105），编号为 1…N1…N。有 N−1N−1 条道路，每条道路连接两个牛棚，并且从任一牛棚均可通过一些道路到达任一其他牛棚。目前，第 jj 个牛棚中有 hjhj 个干草捆（1≤hj≤1091≤hj≤109）。

为使他的奶牛们满意，Farmer John 想移动这些干草，使得每个牛棚都有相同数量的干草捆。他可以选择任何一对由一条道路连接的牛棚，并命令他的农场工人将不超过第一个牛棚中干草捆数量的任意正整数个干草捆从第一个牛棚移动到第二个牛棚。

请求出一个 Farmer John 可以发出的命令序列，以尽可能少的命令数完成这一任务。输入保证存在符合要求的命令序列。

输入样例：

4
2 1 4 5
1 2
2 3
2 4

输出样例：

3
3 2 1
4 2 2
2 1 1

在这个例子中，共有十二个干草捆和四个牛棚，这意味着每个牛棚最后必须有三个干草捆。输出样例中的命令顺序可以用以下的自然语言表述：

1. 从牛棚 33 到牛棚 22，移动 11 个干草捆。
2. 从牛棚 44 到牛棚 22，移动 22 个干草捆。
3. 从牛棚 22 到牛棚 11，移动 11 个干草捆。

供题：Aryansh Shrivastava