Reservoir Water Redistribution

In this problem, you are given a network of reservoirs connected by bidirectional pipelines. Each reservoir initially contains a certain amount of water. If reservoirs are connected (directly or indirectly), water can be redistributed evenly among them. For a connected component with k reservoirs and a total amount of water W, after redistribution every reservoir will contain \(\left\lfloor\frac{W}{k}\right\rfloor\) units of water.

Your task is to determine, for each test case, the maximum possible water level among the reservoirs with the least water in any connected component. In other words, for each connected component, compute the equalized water level and output the maximum among these values.

inputFormat

The input is read from standard input and has the following format:

• The first line contains an integer T representing the number of test cases.
• For each test case:
• The first line contains an integer N, the number of reservoirs.
• The next line contains N space-separated integers, where the i-th integer is the amount of water in the i-th reservoir.
• The following line contains an integer M, the number of bidirectional connections.
• Each of the next M lines contains two integers u and v indicating a connection between reservoir u and reservoir v.

outputFormat

For each test case, output a single line containing the maximum possible water level (after equal redistribution within connected components) among the reservoirs which have the least amount of water in their respective connected component.

## sample

2
3
3 6 9
2
1 2
2 3
4
5 5 5 5
3
1 2
2 3
3 4

6
5

</p>