## MAXISET - Maximal Independent Set

no tags

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274505/problem/G
 English Vietnamese

You are given an unweighted undirected graph G. Each vertex has a positive weighted associated with it. Weight of a set of vertices is defined as the sum of weights of all vertices in the set.

A set of vertices is called independent if there is no edge in the graph with both endpoints on vertices of this set.

A subgraph induced by a set of vertices is a graph with vertex set as the given set of vertices and edges in the original graph with both endpoints in the given set.

If s denotes a set of vertices, then Query(s, G) = Maximal weighted independent set in the subgraph induced by s.

Given q queries and the description of the graph, you are to output the weight of the Maximal weighted independent set corresponding to each of the queries.

### Input

First line contains T, the number of test cases.

Each test case description starts with one line containing 2 integers n and m, denoting the number of vertices and number of edges.

Next line contains n space separated integers denoting the weight of vertices from 0 to n - 1 ( inclusive ).

Next m lines contains two integers u and v ( u != v, 0 ≤ u,v < n ), denoting an undirected edge from u to v.

Next line contains q, the number of querries.

Next q lines contain description of a query. Description of a query starts with an integer denoting the size of set s, followed by the vertices which are members of vertex set s.

### Output

For each test case, output q lines containing the answer to each query. Print a blank line BETWEEN the output of multiple test cases.

### Example

```Input:
2
5 1
1 2 3 4 5
0 1
3
3 0 1 2
3 1 2 3
2 0 1
3 3
1 2 3
0 1
0 2
1 2
1
3 0 1 2

Output:
5
9
2

3
```

### Constraints

Dataset 1: T ≤ 20, n ≤ 30 , m ≤ 1000, q ≤ 1000 , weight_of_a_vertex ≤ 1000 Time limit: 5s

Dataset 2: T ≤ 10, n ≤ 40, m ≤ 1000, q ≤ 100, weight_of_a_vertex ≤ 1000 Time limit: 5s

 Added by: Race with time Date: 2009-02-19 Time limit: 1.183s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ERL JS-RHINO NODEJS PERL6 VB.NET Resource: Code Craft 09