La ferme de Farmer John a $N$ granges ($2\le N\le2\cdot10^5$), numérotées $1\ldots N$, et $N-1$ routes reliant chacune deux granges. On peut aller de toute grange à toute autre. La $j$-ème contient $h_j$ bottes ($1\le h_j\le10^9$).

Pour plaire aux vaches, FJ déplace le foin afin d’égaliser les quantités. Il choisit deux granges reliées et ordonne aux ouvriers de transférer de la première à la seconde un nombre entier positif quelconque de bottes, au plus le stock actuel de la première.

Trouvez une séquence au nombre d’ordres minimal. Son existence est garantie.

Entrée

Première ligne : $N$.

Deuxième : $h_j$ séparés par des espaces, $j=1\ldots N$.

Les dernières $N-1$ lignes : numéros $u_i,v_i$ séparés par un espace, une route bidirectionnelle les relie.

Sortie

Affichez le minimum d’ordres, puis une séquence de cette longueur, un par ligne.

Ordre : trois entiers positifs séparés par des espaces, source, destination, nombre de bottes transférées.

En cas de solutions multiples, affichez-en une quelconque.

Exemples

Entrée 1

4
2 1 4 5
1 2
2 3
2 4

Sortie 1

3
3 2 1
4 2 2
2 1 1

Remarque

Ici $12$ bottes et $4$ granges, donc $3$ chacune à la fin. Les ordres signifient :

1. De $3$ à $2$, transférer $1$ botte.

2. De $4$ à $2$, transférer $2$ bottes.

3. De $2$ à $1$, transférer $1$ botte.

Sous-tâches

• Tests $2\ldots8$ : $N\le5000$.

• Tests $7\ldots10$ : $v_i=u_i+1$.

• Tests $11\ldots16$ : aucune contrainte supplémentaire.

Auteur du problème : Aryansh Shrivastava