You've got an undirected graph, consisting of n vertices and m edges. We will consider the graph's vertices numbered with integers from 1 to n. Each vertex of the graph has a color. The color of the i-th vertex is an integer c_{i}.

Let's consider all vertices of the graph, that are painted some color k. Let's denote a set of such as V(k). Let's denote the value of the neighbouring color diversity for color k as the cardinality of the set Q(k) = {c_{u} :  c_{u} ≠ k and there is vertex v belonging to set V(k) such that nodes v and u are connected by an edge of the graph}.

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 neighbours. Please note, that you want to find such color k, that the graph has at least one vertex with such color.


-----Input-----

The first line contains two space-separated integers n, m (1 ≤ n, m ≤ 10^5) — the number of vertices end edges of the graph, correspondingly. The second line contains a sequence of integers c_1, c_2, ..., c_{n} (1 ≤ c_{i} ≤ 10^5) — the colors of the graph vertices. The numbers on the line are separated by spaces.

Next m lines contain the description of the edges: the i-th line contains two space-separated integers a_{i}, b_{i} (1 ≤ a_{i}, b_{i} ≤ n; a_{i} ≠ b_{i}) — the numbers of the vertices, connected by the i-th edge. 

It is guaranteed that the given graph has no self-loops or multiple edges.


-----Output-----

Print the number of the color which has the set of neighbours with the maximum cardinality. It there are multiple optimal colors, print the color with the minimum number. Please note, that you want to find such color, that the graph has at least one vertex with such color.


-----Examples-----
Input
6 6
1 1 2 3 5 8
1 2
3 2
1 4
4 3
4 5
4 6

Output
3

Input
5 6
4 2 5 2 4
1 2
2 3
3 1
5 3
5 4
3 4

Output
2

Difficulty: interview

Starter code:

Solutions:
n, m = map(int, input().split())
c = [0] + list(map(int, input().split()))
t = {i: set() for i in set(c[1:])}
for i in range(m):
    a, b = map(int, input().split())
    if c[a] != c[b]:
        t[c[a]].add(c[b])
        t[c[b]].add(c[a])
j, k = c[1], 0
for i, s in t.items():
    l = len(s)
    if l >= k: 
        if l > k: j, k = i, l
        elif j > i: j = i
print(j)

n, m = map(int, input().split())
c = [0] + list(map(int, input().split()))
t = {i: [] for i in set(c[1:])}
for i in range(m):
    a, b = map(int, input().split())
    if c[a] != c[b]:
        t[c[a]].append(c[b])
        t[c[b]].append(c[a])
j, k = c[1], 0
for i, s in t.items():
    l = len(set(s))
    if l >= k: 
        if l > k: j, k = i, l
        elif j > i: j = i
print(j)

import sys
v,e = input().split()
v = int(v)
e = int(e)
adj = {}
color= [int(x) for x in input().split()]

for c in color:
	adj[c] = set()
color.insert(0,0)
for i in range(e):
	a,b = input().split()
	a = int(a)
	b = int(b)
	
	if color[a] != color[b]:
		adj[color[a]].add(color[b])
		adj[color[b]].add(color[a])
min_color = sys.maxsize
max_div = 0 
for key in list(adj.keys()):
	if len(adj[key]) > max_div:
		min_color = key
		max_div = len(adj[key])
	elif len(adj[key]) == max_div:
		if key < min_color:
			min_color = key
print(min_color)
#print(adj)

	


3
# D. Colorful Graph
from collections import deque

MAX_COLORS = 10 

def bfs(vertex):
	nonlocal adjlist, visited, colors, dvt, count, idx
	queue = deque()
	queue.append(vertex)
	visited[vertex] = 1
	while queue:
		curv = queue.popleft()
		for v in adjlist[curv]:
			if colors[v] != colors[curv]:
				if colors[curv] not in dvt:
					dvt[colors[curv]] = {colors[v]}
				else:
					dvt[colors[curv]].add(colors[v])
				if len(dvt[colors[curv]]) > count:
					idx = colors[curv]
					count = len(dvt[colors[curv]])
				elif len(dvt[colors[curv]]) == count and colors[curv] < idx:
					idx = colors[curv]
			if visited[v] == 0:
				queue.append(v)
				visited[v] = 1

n, m = [int(x) for x in input().split()]
colors = []
adjlist = [[] for x in range(n)]
dvt = {} 
visited = [0] * n
colors = [int(x) for x in input().split()]
for i in range(m):
	x, y = [int(x) for x in input().split()]
	x -= 1
	y -= 1
	adjlist[x].append(y)
	adjlist[y].append(x)

count = 0
idx = min(colors)
for i in range(n):
	if visited[i] == 0:
		bfs(i)

print(idx)


from collections import defaultdict
n, m = list(map(int, input().split()))
colour = [0] + list(map(int, input().split()))
mx, ans = 0, min(colour[1:])
count = defaultdict(set)
for _ in range(m):
    a, b = list(map(int, input().split()))
    if colour[a] != colour[b]:
        count[colour[a]].add(colour[b])
        count[colour[b]].add(colour[a])
for colour in count:
    if len(count[colour]) > mx:
        mx = len(count[colour])
        ans = colour
    elif len(count[colour]) == mx and colour < ans:
        ans = colour
print(ans)


from collections import defaultdict

get= lambda : list(map(int,input().split()))
n,m=get()
c=list(get())
adj={ i:set() for i in sorted(c)}
for i in range(m):
    a,b=get()
    if c[a-1]!=c[b-1]:
        adj[c[b-1]].add(c[a-1])
        adj[c[a-1]].add(c[b-1])

print(max(adj,key=lambda x:len(adj[x])))
    
    
# http://codeforces.com/problemset/problem/246/D


from collections import defaultdict

n, m = map(int, input().split())
c = list(map(int, input().split()))

res = defaultdict(set)
for _ in range(m):
    u, v = map(lambda x: int(x) - 1, input().split())
    if c[u] != c[v]:
        res[c[u]].add(c[v])
        res[c[v]].add(c[u])

res_count = -1
res_color = -1
for color in c:
    count = res[color]
    if res_count == -1 or res_count < len(count):
        res_count = len(count)
        res_color = color
    elif res_count == len(count) and color < res_color:
        res_color = color

print(res_color)

n,m = list(map(int,input().strip().split()))
color = list(map(int,input().strip().split()))
g = [[] for  i in range(n)]
colors = {i:set() for i in sorted(color)}
for i in range(m):
    u,v =list(map(int,input().strip().split()))
    u -= 1
    v -= 1
    if color[u] != color[v]:
        colors[color[u]].add(color[v])
        colors[color[v]].add(color[u])
print(max(colors,key = lambda x : len(colors[x])))

n,m=list(map(int,input().split()))
l=list(map(int,input().split()))
d={x:set() for x in set(l)}

for i in range(m) :
    a,b=list(map(int,input().split()))
    if l[a-1]!=l[b-1] :
        d[l[a-1]].add(l[b-1])
        d[l[b-1]].add(l[a-1])

d=sorted(d,key=lambda x :(len(d[x]),-x))

print(d[-1])

    


n, m = map(int, input().split())
color = list(map(int, input().split()))

x = list(zip(*[list(map(int, input().split())) for i in range(m)]))
y = x[1]
x = x[0]

ans = dict()

for i in color:
    if i not in ans:
        ans[i] = set()

for i in range(m):
    if color[x[i]-1] != color[y[i]-1]:
        ans[color[x[i]-1]].add(color[y[i]-1])
        ans[color[y[i]-1]].add(color[x[i]-1])

for i in ans:
    Max = i
    break

#print(ans)
MaxLen = len(ans[Max])
for i in ans:
    LAns = len(ans[i])
    if (MaxLen < LAns) or ((MaxLen == LAns) and (Max>i)):
        Max = i
        MaxLen = LAns

print(Max)

n,m=list(map(int,input().split()))
l=list(map(int,input().split()))
d={x:set() for x in set(l)}

for i in range(m) :
    a,b=list(map(int,input().split()))
    if l[a-1]!=l[b-1] :
        d[l[a-1]].add(l[b-1])
        d[l[b-1]].add(l[a-1])

d=sorted(d,key=lambda x :(len(d[x]),-x))

print(d[-1])


n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
a.insert(0,-1)
g=[[] for i in range(n+1)]
for i in range(m):
	u,v=list(map(int,input().split()))
	g[u].append(v)
	g[v].append(u)
#print(g)
div=[0]
for i in range(1,n+1):
	s=set()
	for j in g[i]:
		if a[j]!=a[i]:
			s.add(a[j])
	div.append(s)
#print(div)
c={}
for i in range(1,len(a)):
	if a[i] in c:
		c[a[i]].append(i)
	else:
		c[a[i]]=[i]
#print(c)
m=0
ind=1000000	
for i in c:
	d=set()
	for j in c[i]:
		for k in div[j]:
			d.add(k)
	if len(d)>m:
		ind=i
		m=len(d)
	elif len(d)==m:
		ind=min(ind,i)
print(ind)


n,m=map(int,input().split())
col=list(map(int,input().split()))
cs=set(col)
cnt=[None]*100001
for i in range(100001):
	cnt[i]=set()
for i in range(m):
	u,v=map(int,input().split())
	if(col[u-1]!=col[v-1]):
		cnt[col[u-1]].add(col[v-1])
		cnt[col[v-1]].add(col[u-1])
ans=-1
mx=-1
for i in range(100001):
	if(mx<len(cnt[i]) and i in cs):
		mx=len(cnt[i])
		ans=i
print(ans)

n,m=map(int,input().split())
a=list(map(int,input().split()))
gr=[set() for i in range(n)]
for i in range(m):
	u,v=map(int,input().split())
	gr[u-1].add(v-1)
	gr[v-1].add(u-1)
tr={}
for i in range(max(a)):
	tr[i]=set()
for i in range(n):
	b=a[i]
	for j in gr[i]:
		if a[j]!=b:
			tr[b-1].add(a[j]-1)

ans=0
pos=min(a)
for i in range(max(a)):
	if len(tr[i])>ans:
		ans=len(tr[i])
		pos=i+1

print(pos)

__autor__ = 'Esfandiar'
import sys
input=sys.stdin.readline
from collections import defaultdict
n,m = list(map(int,input().split()))
c = list(map(int,input().split()))
g = [[] for _ in range(n)]
for i in range(m):
    u,v = list(map(int,input().split()))
    g[u-1].append(v-1)
    g[v-1].append(u-1)
color = defaultdict(list)
for u in range(n):
    color[c[u]].append(u)

M = -float('inf')
for k in list(color.keys()):
    seen = dict()
    res=0
    for v in color[k]:
        for u in g[v]:
            if c[u] != k and seen.get(c[u],-1)==-1:
                res+=1
                seen[c[u]]=1
        if res > M:
            M=res
            kk=k
        elif res == M:
            kk=min(kk,k)
print(kk)






'''
8 8
3 3 2 3 3 3 1 3
8 2
6 3
2 3
2 6
5 6
4 2
7 5
1 6
'''



from sys import stdin
from collections import *


def arr_inp(n):
    if n == 1:
        return [int(x) for x in stdin.readline().split()]
    elif n == 2:
        return [float(x) for x in stdin.readline().split()]
    else:
        return list(stdin.readline()[:-1])


def main():
    n, m = arr_inp(1)
    c, ans, ma = arr_inp(1), float('inf'), 0
    mem = defaultdict(set)

    for i in range(m):
        u, v = arr_inp(1)
        u -= 1
        v -= 1
        if c[u] != c[v]:
            mem[c[u]].add(c[v])
            mem[c[v]].add(c[u])

    for i, j in list(mem.items()):
        if len(j) > ma:
            ma = max(ma, len(j))
            ans = i
        if len(j) == ma:
            ans = min(ans, i)

    print(ans if ans != float('inf') else min(c))


def __starting_point():
    main()

__starting_point()

from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
sys.setrecursionlimit(100000)


n,m=mdata()
C=list(mdata())
g=dd(set)
d=dd(set)
for i in range(m):
    a,b=mdata()
    c1=C[a-1]
    c2=C[b-1]
    if c1!=c2:
        d[c1].add(c2)
        d[c2].add(c1)
m=0
ind=min(C)
for i in sorted(d.keys()):
    if len(d[i])>m:
        m=len(d[i])
        ind=i
print(ind)

n, m = list(map(int, input().strip().split()))
color = list(map(int, input().strip().split()))

g = [[] for i in range(n)]

colors = {i:set() for i in sorted(color)}

for i in range(m):
	x, y = list(map(int, input().strip().split()))
	x -= 1
	y -= 1
	#print(color)
	#print(color[x], color[y])
	if color[x] != color[y]:
		colors[color[x]].add(color[y])
		colors[color[y]].add(color[x])
print(max(colors, key = lambda _: len(colors[_])))


from collections import defaultdict
n,m = map(int,input().split())
g = defaultdict(set)
c = list(map(int,input().split()))
for _ in range(m):
    x,y = map(int,input().split())
    if(c[x-1]!=c[y-1]):g[c[x-1]].add(c[y-1])
    if(c[y-1]!=c[x-1]):g[c[y-1]].add(c[x-1])
ma = 0
co = 10**5 + 1      
f = 0   
for i in g:
    ma = max(ma,len(g[i]))
for i in g:
    if(len(g[i])==ma):
        f+=1
        co = min(co,i)
if(f==0):
    co = min(c)
print(co)

from collections import defaultdict
from sys import stdin

input = stdin.readline

class N:
    def __init__(self, c) -> None:
        self.c = c
        self.ch = []


def __starting_point():
    n, m = list(map(int, input().split()))
    carr = list(map(int, input().split()))
    arr = [N(x) for x in carr]

    for _ in range(m):
        a, b = list(map(int, input().split()))
        arr[a - 1].ch.append(arr[b - 1])
        arr[b - 1].ch.append(arr[a - 1])

    for x in arr:
        x.ch = list([y for y in x.ch if y.c != x.c])

    dct = defaultdict(lambda: set())

    for x in arr:
        for y in x.ch:
            if y.c != x.c:
                dct[x.c].add(y.c)

    narr = []

    for key, value in list(dct.items()):
        narr.append((key, len(value)))

    narr.sort(key=lambda x: x[1], reverse=True)

    if narr:
        narr = list(sorted([x for x in narr if x[1] == narr[0][1]], key=lambda x: x[0]))
        print(narr[0][0])
    else:
        print(min(carr))

__starting_point()

import sys
input=sys.stdin.readline
n,m=list(map(int,input().split()))
l=list(map(int,input().split()))
d={x:set() for x in set(l)}

for i in range(m) :
    a,b=list(map(int,input().split()))
    if l[a-1]!=l[b-1] :
        d[l[a-1]].add(l[b-1])
        d[l[b-1]].add(l[a-1])

d=sorted(d,key=lambda x :(len(d[x]),-x))

print(d[-1])


import sys
input=sys.stdin.readline
from collections import defaultdict
def dfs(i):
	st=[i]
	while st:
		x=st.pop()
		if vis[x]:continue
		vis[x]=1
		for v in sorted(g[x]):
			if c[x-1]!=c[v-1]:d[c[x-1]].add(c[v-1])
			if not vis[v]:
				st.append(v)

n,m=map(int,input().split())
c=list(map(int,input().split()))
g=[[] for i in range(n+1)]
for i in range(m):
	x,y=map(int,input().split())
	g[x].append(y)
	g[y].append(x)
d=defaultdict(set)
vis=[0]*(n+1)
for i in range(1,n+1):
	if vis[i] == 0:
		dfs(i)
k=sorted(d.keys(),key=lambda i:(len(d[i]),-i))
if not k:print(min(c))
else:print(k[-1])

from collections import defaultdict
l=lambda :map(int,input().split())
n,m=l()
c=list(l())
graph=defaultdict(set)
for i in range(m):
    a,b=l()
    if c[a-1]==c[b-1]:
        continue
    graph[c[a-1]].add(c[b-1])
    graph[c[b - 1]].add(c[a - 1])
d,f=min(c),0
for i in sorted(graph):
    h=len(graph[i])
    if h>f:
        f=h
        d=i
print(d)

from collections import defaultdict
l=lambda :map(int,input().split())
n,m=l()
c=list(l())
graph=defaultdict(set)
for i in range(m):
    a,b=l()
    if c[a-1]==c[b-1]:
        continue
    graph[c[a-1]].add(c[b-1])
    graph[c[b - 1]].add(c[a - 1])
d=sorted(graph,key=lambda x:(-len(graph[x]),x))
print(d[0] if d else min(c))