## INTSS - Internally Stable Sets

no tags

A weighted finite undirected graph is a triple G = (V, E, w) consisting of vertex set V, edge set , and vertex weighting function w such that and . For and , N(u) and N(K) will denote the neighboring vertex sets of u and K respectively, formally defined as: A vertex set satisfying is called internally stable (also known as independent or anti-clique). In this problem you must find an internally stable set B such that w(B) = max{w(S)}, where S belongs to the set of all internally stable sets of that graph.

### Input

t – the number of test cases [t <= 100]
n k – [n – number of vertices (2 <= n <= 200), k – number of edges (1 <= k <= n*(n-1)/2)]
then n numbers follows (wi - the weight of i-th vertex) [ 0 <= wi <= 2^31-1]
then k pairs of numbers follows denoting the edge between the vertices (si sj edge between i-th and j-th verices) [1 <= si, sj <= n]

### Output

For each test case output MaxWeight – the weight of a maximum internally stable set of the given graph. [ 0 <= MaxWeight <= 2^31-1]

### Example

```Input:
2
5 6
10 20 30 40 50
1 2
1 5
2 3
3 4
3 5
4 5

4 4
10 4 10 14
1 2
2 3
3 4
4 1

Output:
70
20
``` gautams: 2015-07-17 06:41:32 I have solved the problem but it is exceeding time limit. Please help. Do I have to know any specific thing in graph theory ?? Faisal Khan: 2013-07-20 10:11:11 Last edit: 2013-07-20 10:11:38 Alex: 2013-01-02 18:52:01 Isn't this an NP-hard problem? Leonardo Lopez: 2012-10-02 19:17:44 This is a tutorial exercise? [Trichromatic] XilinX: 2009-04-13 03:07:17 Hard versions of this problem are MIS & MAXISET (Actually, both these two codes mean "Maximum Independent Set" :-)