Maximum Coins in Connected Caves

You are given a set of N caves and M tunnels connecting them. Each cave i holds a certain number of coins. The tunnels form an undirected graph where each tunnel connects two distinct caves. The task is to determine the maximum number of coins that can be collected by traversing through any connected component of caves. In other words, identify the connected component with the highest sum of coins.

Details:

• Let \(N\) be the number of caves and \(M\) be the number of tunnels.
• You are given a list of coin amounts for each cave.
• You are also given a list of tunnels, where each tunnel is described by two integers representing the 1-indexed caves it connects.

Your goal is to compute \(\max\{\text{sum of coins in a connected component}\}\).

inputFormat

The input is given via standard input (stdin) and has the following format:

1. The first line contains two space-separated integers \(N\) and \(M\), where \(N\) is the number of caves and \(M\) is the number of tunnels.
2. The second line contains \(N\) space-separated integers representing the number of coins in each cave.
3. The next \(M\) lines each contain two space-separated integers \(u\) and \(v\) indicating that there is a tunnel connecting cave \(u\) and cave \(v\) (1-indexed).

outputFormat

Output a single integer to standard output (stdout): the maximum number of coins that can be collected from any connected group of caves.

4 4
5 3 4 7
1 2
2 3
3 4
4 1

19