#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTICES 250
#define ADJ(v1, v2) adjacent[(v1) * num_vertices + (v2)]
int num_test_cases; //<! Number of test cases
int num_edges; //<! Number of edges
int num_vertices; //<! Number of vertices
int weights[MAX_VERTICES]; //<! Vertex weights
int colors[MAX_VERTICES]; //<! Vertex colors
int adjacent[MAX_VERTICES * MAX_VERTICES - 1]; //<! Flattened adjacency matrix
int cur_clique[MAX_VERTICES]; //<! Current clique
int cur_clique_size; //<! Size of the current clique
int cur_clique_weight; //<! Weight of the current clique
int best_clique_weight; //<! Weight of the best clique
/*!
* Expand each vertex of the given graph against the current clique.
*/
void expand(int *graph, int graph_size) {
bool any_expanded = false;
/* Loop through each vertex in the graph */
for(int i = 0; i < graph_size; i++) {
/* See if it is expandable -- if it is adjacent to all vertices in the clique */
bool expandable = true;
for(int j = 0; j < cur_clique_size; j++) {
if(!ADJ(graph[i], cur_clique[j])) {
expandable = false;
break;
}
}
if(expandable) {
any_expanded = true;
/* Add it to the current clique */
cur_clique[cur_clique_size++] = graph[i];
cur_clique_weight += weights[graph[i]];
/* Build a new graph of all vertices in this graph adjacent to it */
int *next_graph = malloc(graph_size * sizeof(int));
int next_graph_size = 0;
for(int j = 0; j < graph_size; j++) {
if(j != i && ADJ(graph[i], graph[j])) {
next_graph[next_graph_size++] = graph[j];
}
}
/* Expand the next graph */
expand(next_graph, next_graph_size);
/* Destroy the temporary graph */
free(next_graph);
/* Remove it from the current clique */
cur_clique_size--;
cur_clique_weight -= weights[graph[i]];
}
}
if(!any_expanded && cur_clique_weight > best_clique_weight) {
best_clique_weight = cur_clique_weight;
}
}
/*!
* Find the maximum clique
*/
void max_clique()
{
/* Initialize */
best_clique_weight = 0;
cur_clique_size = 0;
cur_clique_weight = 0;
/* Expand the full graph */
int * full_graph = malloc(num_vertices * sizeof(int));
for(int i = 0; i < num_vertices; i++) {
full_graph[i] = i;
}
expand(full_graph, num_vertices);
}
int main(int argc, char **argv)
{
scanf("%d", &num_test_cases);
for(int i = 0; i < num_test_cases; i++) {
/* Reset data */
scanf("%d %d", &num_vertices, &num_edges);
for(int j = 0; j < num_vertices * num_vertices - 1; j++) {
adjacent[j] = 1;
}
memset(colors, 0, num_vertices);
/* Read vertices */
for(int j = 0; j < num_vertices; j++) {
scanf("%d", &weights[j]);
}
/* Read edges */
for(int j = 0; j < num_edges; j++) {
int v1, v2;
scanf("%d %d", &v1, &v2);
ADJ(v1 - 1, v2 - 1) = 0;
ADJ(v2 - 1, v1 - 1) = 0;
}
/* Do the work */
max_clique();
/* Show the results */
printf("%d\n", best_clique_weight);
}
return 0;
}