Sheepland 是一个拥有 $n$ 个城市的国家。有 $n-1$ 条道路连接着各对城市。道路 $j$ 直接连接城市 $u[j]$ 和 $v[j]$。最初，仅使用这些道路，可以从任何城市到达其他任何城市。

Sheepland 的所有 $n-1$ 条道路都计划进行翻新。根据翻新计划，每条道路 $j$ 将处于以下四种状态之一：

1. 双向：来自城市 $u[j]$ 和 $v[j]$ 的市民都可以穿过这条道路到达另一个城市。
2. 从城市 $u[j]$ 到城市 $v[j]$ 的单向：只有来自城市 $u[j]$ 的市民可以穿过这条道路到达城市 $v[j]$。
3. 从城市 $v[j]$ 到城市 $u[j]$ 的单向：只有来自城市 $v[j]$ 的市民可以穿过这条道路到达城市 $u[j]$。
4. 关闭：来自城市 $u[j]$ 或 $v[j]$ 的市民都不能穿过这条道路到达另一个城市。

不幸的是，翻新计划丢失了！

为了尝试恢复它，你询问了每个城市的市长，在翻新计划下，从他们的城市可以到达多少个城市。第 $i$ 个城市的市长回答了 $l[i]$。然而，一些市长可能提供了错误的值。

如果存在一个序列 $c_1, c_2, c_3, \dots, c_k$，使得 $c_1 = u$，$c_k = v$，并且对于所有 $1 \le x \le k-1$，从 $c_x$ 到 $c_{x+1}$ 存在一条可通行的道路，则称城市 $v$ 是从城市 $u$ 可到达的。特别地，城市本身是可到达的。

请帮助 Sheepland 确定是否存在一个翻新计划，使其与所有市长报告的从每个城市可到达的城市数量一致！

输入格式

你的程序必须从标准输入读取数据。

第一行包含一个整数 $n$。

第二行包含 $n$ 个空格分隔的整数 $l[1], l[2], \dots, l[n]$。

接下来的 $n-1$ 行，每行包含两个空格分隔的整数。第 $j$ 行包含 $u[j]$ 和 $v[j]$。

输出格式

你的程序必须输出到标准输出。

如果存在一个与所有市长报告的从每个城市可到达的城市数量一致的翻新计划，输出 YES，否则输出 NO。

子任务

对于所有测试用例，输入满足以下范围：

• $1 \le n \le 5000$
• $1 \le l[i] \le n$，对于所有 $1 \le i \le n$
• $1 \le u[j], v[j] \le n$，对于所有 $1 \le j \le n-1$
• $u[j] \neq v[j]$，对于所有 $1 \le j \le n-1$
• 最初，仅使用道路，可以从任何城市到达其他任何城市。

你的程序将在满足以下限制的输入实例上进行测试：

样例

样例输入 1

9
5 2 3 5 2 3 1 1 1
1 4
4 5
2 5
3 6
5 6
6 9
7 8
4 7

样例输出 1

YES

样例输入 2

9
5 2 3 5 2 3 1 1 2
1 4
4 5
2 5
3 6
5 6
6 9
7 8
4 7

样例输出 2

NO

样例输入 3

7
3 3 1 3 2 1 2
3 4
1 2
6 2
7 3
5 6
4 2

样例输出 3

YES