Tree Division

题号：NC237070
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

You are given a tree of $n$ nodes, the i-th node has value $a_i$ .
Define a node $t$ is valid, if you can divide the $n$ nodes into two sets $A$ and $B$ , so that the following condition would hold:

$\forall u,v\in A(u\neq v)$ , if $u$ is on the path from $t$ to $v$ , then $a_u<a_v$
$\forall u,v\in B(u\neq v)$ , if $u$ is on the path from $t$ to $v$ , then $a_u>a_v$

You need to find out whether the node $1$ is valid.

输入描述:

The first line contains one integer .
The second line contains  integers .
The next  lines each contains two integers  and  , denoting an edge between node  and .

输出描述:

Output  if node  is valid, otherwise print .

示例1

输入

复制

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

输出

复制

YES

说明

In this case, node  is valid.
A possible division is: ,.

示例2

输入

复制

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

输出

复制

NO