陈教授是一位图着色问题专家。现在，他向你展示了一个带颜色的有向图，并声称图中每一条长度不超过 $k$ 的简单路径都包含互不相同的颜色。

请检查陈教授的断言是否正确。

†：简单路径是指一个由互不相同的顶点 $u_1, u_2, \dots, u_L$ 组成的序列，使得对于每个 $i \in [1, L - 1]$，都存在一条从 $u_i$ 到 $u_{i+1}$ 的边。该简单路径的长度为 $L$。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试数据的组数。对于每组测试数据：

第一行包含三个整数 $n, m, k$ ($1 \le n, k \le 10^5, 0 \le m \le 10^5$)，分别表示顶点数、边数以及陈教授给出的参数 $k$。

第二行包含 $n$ 个整数 $c_i$ ($1 \le c_i \le 50$)，表示每个顶点的颜色。

接下来的 $m$ 行，每行包含两个整数 $u_j, v_j$ ($1 \le u_j, v_j \le n$)，表示图中的一条有向边。

保证所有测试数据的 $n$ 之和与 $m$ 之和均不超过 $10^5$。

输出格式

对于每组测试数据，如果陈教授的断言正确，输出一行 "YES"；否则，输出一行 "NO"。

样例

输入 1

3
3 2 2
1 2 1
1 2
2 3
3 3 2
1 2 1
1 2
2 3
1 3
3 3 50
1 1 2
1 2
2 3
1 3

输出 1

YES
NO
NO