Max Coins on Path

You are given an undirected graph with (N) vertices and (M) edges. Each vertex (i) is assigned a number of coins (c_i). Your task is to determine the maximum number of coins that can be collected along any valid path in the graph. A valid path is a sequence of vertices where each vertex is visited at most once. Note that the graph may be disconnected, so you must consider all connected components. In each test case, output the maximum coin sum obtainable by starting at some vertex and traversing a sequence of adjacent vertices, summing their coins as you go.

The input format is as follows:

• The first line contains an integer \(T\), the number of test cases.
• For each test case:
  • The first line contains two space-separated integers \(N\) and \(M\): the number of vertices and edges, respectively.
  • The second line contains \(N\) space-separated integers \(c_1, c_2, \ldots, c_N\) where \(c_i\) is the number of coins at vertex \(i\).
  • The following \(M\) lines each contain two integers \(u\) and \(v\) indicating there is an edge between vertices \(u\) and \(v\) (1-indexed).

inputFormat

Input is read from standard input (stdin). The first line contains an integer (T) representing the number of test cases. For each test case:

1. The first line contains two integers (N) and (M), representing the number of vertices and edges.
2. The second line contains (N) integers, where the (i)-th integer represents the number of coins at vertex (i).
3. Each of the next (M) lines contains two integers (u) and (v) indicating an edge between vertices (u) and (v) (vertices are 1-indexed).

outputFormat

Output to standard output (stdout). For each test case, output a single integer on a new line which is the maximum number of coins that can be collected following any valid path.## sample

2
4 5
5 10 15 20
1 2
2 3
3 4
1 3
2 4
3 3
3 2 5
1 2
1 3
2 3

50
10