URI Online Judge | 1702

# Graph Coloring

By Contest Road to Fortaleza V 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