Lưu ý: Giới hạn thời gian là 4 giây. Giới hạn bộ nhớ là 512MB.

Nông dân John có \(N\) chuồng bò \((2 \le N \le 2 \times 10^5)\) được đánh số \(1 \dots N\). Có \(N - 1\) con đường hai chiều nối các cặp chuồng bò, và từ một chuồng bò có thể đi đến \(N - 1\) chuồng còn lại. Hiện tại, chuồng \(j\) có \(h_j\) kiện có khô \((1 \le h_j \le 10^9)\).

Để làm hài lòng lũ bò, nông dân John muốn di chuyển các kiện này sao cho số lượng cỏ khô mà các chú bò có là bằng nhau. Bác ta có thể chọn \(1\) cặp chuồng bất kì có đường nối giữa chúng và ra lệnh cho cấp dưới di chuyển các kiện hàng với số lượng nguyên dương bất kì bé hơn hoặc bằng so với số kiện cỏ hiện tại đang có trong chuồng sang chuồng còn lại.

Hãy xác định dãy các mệnh lệnh để nông dân John có thể hoàn thành nhiệm vụ sao cho độ dài dãy là bé nhất. Dữ liệu đảm bảo thấy rằng đáp án luôn tồn tại.

Input

• Dòng đầu tiên là số \(N\).
• Dòng thứ hai là \(N\) số \(h_1, h_2, \dots, h_N\).
• \(N - 1\) dòng cuối cùng là các cặp \(u_i, v_i\) thoả mãn có một đường nối giữa chuồng \(u_i\) và chuồng \(v_i\).

Output

• Dòng đầu tiên là số lượng mệnh lệnh ít nhất bác John cần thực hiện (Gọi là \(T\)).
• Trong \(T\) dòng tiếp theo, dòng thứ \(i\) là bộ ba số \(a_i, b_i, c_i\), trong đó: \(a_i\) là chuồng lấy kiện cỏ, \(b_i\) là chuồng các kiện cỏ được chuyển đến, \(c_i\) là số lượng kiện cỏ được lấy.

Scoring

• Subtask \(1\): \(N \le 5000\).
• Subtask \(2\): \(v_i = u_i + 1 \forall i\).
• Subtask \(3\): Không còn ràng buộc.

4
2 1 4 5
1 2
2 3
2 4

3
3 2 1
4 2 2
2 1 1