#P1637E. Best Pair
Best Pair
Description
You are given an array of length . Let be the number of elements from the array which are equal to . Let's also define as .
Also you are given bad pairs . Note that if is a bad pair, then is also bad.
Your task is to find the maximum value of over all pairs , such that , that this pair is not bad, and also that and each occur in the array . It is guaranteed that such a pair exists.
The first line contains a single integer () — the number of test cases.
The first line of each test case contains two integers and (, ) — the length of the array and the number of bad pairs.
The second line of each test case contains integers () — elements of the array.
The -th of the next lines contains two integers and (), which represent a bad pair. It is guaranteed that no bad pair occurs twice in the input. It is also guaranteed that and .
It is guaranteed that for each test case there is a pair of integers , , that is not bad, and such that both of these numbers occur in .
It is guaranteed that the total sum of and the total sum of don't exceed .
For each test case print a single integer — the answer to the problem.
Input
The first line contains a single integer () — the number of test cases.
The first line of each test case contains two integers and (, ) — the length of the array and the number of bad pairs.
The second line of each test case contains integers () — elements of the array.
The -th of the next lines contains two integers and (), which represent a bad pair. It is guaranteed that no bad pair occurs twice in the input. It is also guaranteed that and .
It is guaranteed that for each test case there is a pair of integers , , that is not bad, and such that both of these numbers occur in .
It is guaranteed that the total sum of and the total sum of don't exceed .
Output
For each test case print a single integer — the answer to the problem.
Samples
Note
In the first test case , , occur in the array.
- . But is bad so we ignore it.
- .
- .
The answer to the problem is .