E. Travel
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Another vacation is coming. Mandy and brz plan to travel in some cities this time. They have $$$T$$$ plans.

In each plan, they have $$$n$$$ cities as alternatives. There are $$$m$$$ directed roads between cities, and all the cities and roads form a DAG (Directed acyclic graph). Every city has a charm $$$a_i$$$. They expect to travel from city $$$1$$$ to city $$$n$$$. Mandy thinks if they visit three cities $$$x,y,z$$$ consecutively and $$$a_x+a_y+a_z\leq k$$$, it would be a terrible route.

Thus brz needs to find a route from city $$$1$$$ to city $$$n$$$ which is not terrible. Since it is too hard for him, he turns to you for help. And you only need to tell him whether the route exists or not.

Input

The first line contains one integer $$$T~(1\leq T\leq 10^3)$$$——the number of plans.

In each plan, the first line contains three integer $$$n,m,k~(2\leq n\leq 3\times 10^5, 0\leq m\leq 3\times 10^5,1\leq k\leq 10^9)$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\cdots, a_n~(1\leq a_i\leq 10^9)$$$.

Each of the following $$$m$$$ lines contains two integer $$$u_i,v_i~(1\leq u_i,v_i\leq n)$$$, denoting a directed road from $$$u_i$$$ to $$$v_i$$$.

It is guaranteed that the given graph is a DAG and every road is distinct (in one plan), and $$$\sum n\leq 3\times 10^5, \sum m \leq 3\times 10^5$$$.

Output

Print $$$T$$$ lines. If there exists a route that is not terrible, print Yes. Otherwise print No.

Example
Input
2
3 2 5
1 2 3
1 2
2 3
3 2 6
1 2 3
1 2
2 3
Output
Yes
No