Có \(N\) thành phố trong một đất nước được kết nối bằng đường hai chiều. Một số thành phố là thành phố loại 1, một số là loại 2 và một số chưa được xếp loại. Đất nước được đảm bảo rằng có chứa ít nhất một thành phố loại 1, một thành phố loại 2. Bạn chọn một con đường và loại bỏ nó ra khỏi hệ thống đường đi khiến đất nước bị chia thành hai phần. Đó sẽ là một con đường đẹp nếu nó chia đất nước thành hai phần mà kết quả mỗi phần không chứa các thành phố của cả hai loại 1 và 2.

Yêu cầu: Bạn hãy tính số lượng những con đường đẹp.

Input

• Dòng đầu tiên chứa số nguyên \(N (3 \leq N \leq 3 \times 10^5)\), số thành phố. Các thành phố được dán nhãn với số lượng từ 1 đến \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,\cdots,a_n\) \((0 \leq a_i \leq 2)\) là loại của các thành phố với:
  • \(a_i=1\) có nghĩa là thành phố loại 1
  • \(a_i=2\) có nghĩa là thành phố loại 2
  • \(a_i=0\) có nghĩa là thành phố chưa được xếp loại
• Dòng thứ \(i\) của \(N−1\) dòng tiếp theo chứa hai số nguyên \(v_i,u_i (1 \leq v_i,u_i \leq N)\) – các cạnh của cây.

Output

• Đưa ra một số nguyên duy nhất là số lượng đường đẹp

Example

5
2 0 0 1 2
1 2
2 3
2 4
2 5 

1