## MAXISET - Maximal Independent Set

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 2Output: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 |