gdl-gokuldhaam-diversity-league-5

Gokuldhaam society is famous for their diversity. This time they are up with a contest on Color-Diversity. 

Given N houses numbered from 1,2,....N. House numbered i is colored with some color C[i]. Let's consider all houses, that are painted some color k. Set of all such houses with color k is H(k).

Let's the neighboring color diversity for color k as the cardinality of the set Q(k) ={C[u] : C[u] != k and there is a house v belonging to set H(k) such that u and v are adjacent(connected)}. Houses are connected with M edges.

Your task is to find such color k, which makes the cardinality of set Q(k) maximum. In other words, you want to find the color that has the most diverse neighbors. Please note, that you want to find such color k, that at least one house is having such color.
If there are multiple colors with same maximum count then select the color with lowest index.

INPUT

      First line contains an integer T, the number of test cases.

      Each test case is:
       First line with two integers N and M, Number of houses and edges connecting them.

       Second line contains N space saparated integers C[1], C[2]...., C[n], the color of houses.

       Next M lines with two integers u, v showing House Number u is connected to v. Connection is bidirectional.

OUTPUT

      T lines with the winner color-index from each test case.

CONSTRAINTS

        0<T<20

        0<N<100001

        0<M<200001

        0<C[i]<100001

        N*T will never exceed 100000
Register for IndiaHacksSAMPLE INPUT
2
6 5
2 2 2 1 2 2
4 5
4 2
5 2
4 1
2 3
6 6
2 2 3 4 6 9
1 2
3 2
1 4
4 3
4 5
4 6

SAMPLE OUTPUT
1
4

Register for IndiaHacks

Source: hackerearth | Difficulty: MEDIUM


Solutions: