Chloe và những phần quà

Cho một cây có gốc gồm $n$ đỉnh, gốc là đỉnh $1$. Mỗi đỉnh $i$ có một trọng số $a_i$ (có thể âm, dương hoặc bằng $0$).

Với một đỉnh $v$ bất kỳ, gọi cây con của $v$ là tập hợp gồm $v$ cùng tất cả các đỉnh nằm phía dưới $v$ (con, cháu... của $v$). Tổng của một cây con là tổng trọng số của mọi đỉnh thuộc cây con đó.

Hãy chọn ra hai đỉnh khác nhau $u$ và $v$ sao cho cây con của $u$ và cây con của $v$ không giao nhau (không có đỉnh nào thuộc cả hai cây con). Trong tất cả các cách chọn như vậy, hãy tìm giá trị lớn nhất của tổng hai cây con đã chọn.

Nếu không tồn tại cặp đỉnh nào thỏa mãn, in ra Impossible.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số đỉnh của cây.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ — trọng số của các đỉnh.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$ ($u\ne v$) cho biết có một cạnh nối hai đỉnh $u$ và $v$. Một trong hai đỉnh là cha của đỉnh còn lại; thứ tự có thể tùy ý.

Dữ liệu đảm bảo mọi đỉnh đều thuộc cây có gốc là đỉnh $1$.

Dữ liệu ra

In ra một số nguyên — tổng lớn nhất có thể đạt được, hoặc Impossible nếu không thể chọn được cặp đỉnh hợp lệ.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $-{10}^9\le a_i\le {10}^9$
• $1\le u,v\le n$, $u\ne v$

Ví dụ