Hard Problem

This is the most tough task in this contest, do not try it until you solve all the other tasks or you feel boring on others. Given an undirected graph, you are to find out a subgraph of it so that the degree of the i-th node in the subgraph is the given integer D_i. The subgraph is a subset of edges and all vertexes are reserved. Notice that the graph may be disconnected, and two edges may connect the same vertexes, but no self cyclic exists.

The input contains several test cases, the first line of the input contains an integer T denoting the number of test cases.
For each test case, the first line contains two integers N and M, denoting the number of vertexes and number of edges in the graph. (1 <= N <= 50, 1 <= M <= 200)
For the next M lines, each line contains two integers X and Y, denote there is a edge between X-th node and Y-th node. (1 <= X, Y <= N)
For the last N lines, each line contains a single integer D_i, denote the degree of i-th node in the subgraph.

For each test case, if the subgraph exist, output "YES", otherwise output "NO". See sample output for further details

2
4 4
1 2
3 4
2 3
1 4
1
2
1
0
4 5
2 1
1 2
2 3
3 4
3 4
1
0
1
0

Case 1: YES
Case 2: NO

HyperHexagon

HyperHexagon's Summer Gift (Original tasks)