URI Online Judge | 1702

Graph Coloring

By Contest Road to Fortaleza V BR Brazil

Timelimit: 2

Let G be a simple graph with N colored vertices and M edges. We want to know whether it is possible to add exactly P new edges to G so that the resulting graph is simple, connected and none of its edges connect two vertices of the same color.

Input

The input consists of multiple test cases. The first line contains the number of test cases T ( T <= 70). Each test case begins with a line containing 4 integers in the following order: the number of vertices N (1 <= N <= 10^3), the number of edges in the original graph M (0 <= M <= 10^5), the number of edges to be inserted P ( 0 <= P <= 10^6) and the number of colors K (1 <= K <= 10^3). The following line has N numbers Xi indicating the color for the i-th vertex (1 <= Xi <= K). The following M lines contains a pair of integers (V_i, V_j) stating the presence of an edge between vertex V_i and V_j  (1 <= V_i,V_j <= N).

Output

For each test, output a single line with "Y" (without  quotes) if it is possible to draw such graph or "N" otherwise.

Sample Input Sample Output

2
4 2 1 2
1 1 2 2
1 3
2 4
4 1 1 2
1 1 2 2
1 3

Y

N