Farmer Johns Hof hat $N$ Scheunen ($2\le N\le2\cdot10^5$), nummeriert $1\ldots N$, und $N-1$ Straßen zwischen je zwei. Jede Scheune ist von jeder erreichbar. Scheune $j$ hat $h_j$ Heuballen ($1\le h_j\le10^9$).

Um die Kühe zu erfreuen, bewegt FJ Heu bis alle gleich viele Ballen haben. Er wählt zwei durch eine Straße verbundene Scheunen und befiehlt Arbeitern, beliebig viele positive ganzzahlige Ballen von der ersten zur zweiten zu bewegen, höchstens den aktuellen Bestand der ersten.

Finde eine Befehlsfolge mit minimaler Zahl. Ihre Existenz ist garantiert.

Eingabe

Erste Zeile: $N$.

Zweite: $h_j$ mit Leerzeichen, $j=1\ldots N$.

Letzte $N-1$ Zeilen: Scheunennummern $u_i,v_i$ mit Leerzeichen, eine Straße in beide Richtungen.

Ausgabe

Gib die minimale Befehlszahl und eine Folge dieser Länge aus, einen pro Zeile.

Befehl: drei positive ganze Zahlen mit Leerzeichen, Quelle, Ziel und bewegte Ballenzahl.

Bei mehreren Lösungen gib eine beliebige aus.

Beispiele

Eingabe 1

4
2 1 4 5
1 2
2 3
2 4

Ausgabe 1

3
3 2 1
4 2 2
2 1 1

Hinweis

$12$ Ballen und $4$ Scheunen, am Ende je $3$. Die Befehle lauten:

1. Von $3$ nach $2$ bewege $1$ Ballen.

2. Von $4$ nach $2$ bewege $2$ Ballen.

3. Von $2$ nach $1$ bewege $1$ Ballen.

Teilaufgaben

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

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

• Tests $11\ldots16$: keine weiteren Einschränkungen.

Autor der Aufgabe: Aryansh Shrivastava