21636_Subse

A simple graph is an undirected graph. It has no self loop edges and no parallel edges, which means that no two distinct edges have exactly the same pair of ends. Given a simple graph, in which each vertex has a weighted value, and each edge can only belong to at most one simple cycle. Your task is to find a set of vertices, no two vertices in this set are adjacent, and the sum of weights of the vertices in the set should be maximized.

Input contains several cases.

The first line of each case contains an integer n ( 1 ≤ n ≤ 10 000 ), which is the number of nodes.

The second line contains n integers (each equal to or larger than 0, less than 10000 ). The i-th number is the weight of the i-th node.

The third line contains an integer m, which is the number of edges.

Each of the following m lines contains two integers a and b, 1 ≤ a, b ≤ n, representing that there is an edge between a and b.

The input ended by n=0.

Output one integer for each input case, representing the total weight of the largest independent subset.

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

3