Nông trại Farmer John có $N$ chuồng ($2\le N\le2\cdot10^5$), số $1\ldots N$, và $N-1$ đường nối các cặp. Từ bất kỳ chuồng nào tới được mọi chuồng khác. Chuồng $j$ có $h_j$ bó cỏ ($1\le h_j\le10^9$).

Để bò vui, FJ chuyển cỏ cho mọi chuồng bằng nhau. Chọn hai chuồng nối bằng đường và ra lệnh công nhân chuyển từ thứ nhất sang thứ hai một số nguyên dương bó bất kỳ không quá số hiện tại trong thứ nhất.

Tìm chuỗi ít lệnh nhất. Bảo đảm tồn tại.

Dữ liệu vào

Dòng đầu $N$.

Dòng hai $h_j$ cách bằng dấu cách, $j=1\ldots N$.

$N-1$ dòng cuối có số $u_i,v_i$ cách bằng dấu cách, đường hai chiều nối chúng.

Dữ liệu ra

In số lệnh ít nhất rồi chuỗi đúng độ dài, mỗi dòng một lệnh.

Lệnh là ba số nguyên dương cách bằng dấu cách: nguồn, đích, số bó chuyển.

Nếu nhiều lời giải, in bất kỳ.

Ví dụ

Dữ liệu vào 1

4
2 1 4 5
1 2
2 3
2 4

Dữ liệu ra 1

3
3 2 1
4 2 2
2 1 1

Ghi chú

$12$ bó và $4$ chuồng, cuối cùng mỗi chuồng $3$. Lệnh nghĩa là:

1. Từ $3$ sang $2$ chuyển $1$ bó.

2. Từ $4$ sang $2$ chuyển $2$ bó.

3. Từ $2$ sang $1$ chuyển $1$ bó.

Nhiệm vụ con

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

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

• Ca $11\ldots16$: không ràng buộc thêm.

Tác giả bài toán: Aryansh Shrivastava