Statement is not available in English language
J. 收藏宝石
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

小 L 是一名魔法师，他收藏了 n 个宝石。为了方便展示，他用 m 条绳索将这些宝石与房梁相互连接。其中，第 i 个宝石可以视为第 i 个节点，而房梁是一个编号为 0 的特殊节点。

当小 L 需要使用某个宝石时，他会选择一个宝石，并 切断所有与该宝石相连的绳索 。

若此操作恰好使得 仅有一个宝石 失去与房梁的连接（即被取下），则称这次操作是 合法的 ，且该宝石被取下。

每个宝石都有一个自己的价值 ai。小 L 想知道， 以当前的绳索连接方式，是否存在一种取下顺序 ，能使他每次都能合法取下 当前剩余宝石中价值最大的宝石之一 。

Input

第一行包含三个整数 n, m, k (1 ≤ n, m, k ≤ 105)，分别表示宝石数量和绳索数量，以及宝石价值的上界。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ k)，其中 ai 表示第 i 个宝石的价值。

接下来 m 行，每行包含两个整数 x, y (0 ≤ x, y ≤ n)，表示第 x 个节点与第 y 个节点之间有一条绳索连接。特殊地，第 0 号节点表示 房梁 而不是宝石。

保证所有宝石均与房梁连通，保证任意两个节点之间至多只有一条绳索连接，没有绳索连接同一个节点。

Output

如果符合要求的合法取下顺序，输出 "YES"，否则输出 "NO" 。

你可以以任意大小写输出 "YES" 和 "NO"（例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 将被识别为肯定的回答）。

Examples
Input
2 3 10
10 1
0 1
1 2
2 0
Output
YES
Input
2 2 10
10 1
0 1
1 2
Output
NO
Input
6 10 3
1 3 2 2 2 3
0 1
0 2
0 5
1 3
1 4
2 3
2 5
3 6
4 6
5 6
Output
YES
Note

测试样例三的图如下所示：