The growth of Computer Science has forced the scientific community to award Nobel Prize in CS starting from this year.

Chef knows that the Nobel community is going to award the prize to that person whose research is different from others (ie. no other researcher should work on the same topic). If there are multiple such people, who work on unique topics, then they will all share the prize. It might also happen that no one wins this time.

Chef also knows the N researchers which the community who will be considered for the prize, and the topics in which each of them work.

In total the CS field can be divided into M broad topics. Given the topics in which each of the N researchers are working on, in the form of an array A, and given that Chef can master any topic instantly, find whether he can win the prize. That is, can the Chef choose to work on some topic which will guarantee that he will win the prize? Chef doesn't mind sharing the prize with others.

------ Input Format ------ 

- First line will contain T, number of testcases. Then the testcases follow. 
- Each testcase contains of two lines of input. 
- First line contains two space separated integers N, M, number of researchers excluding Chef and total number of fields respectively.
- Second line contains N space separated integers A_{1}, A_{2}, \ldots A_{N}, research topic of the researchers.

------ Output Format ------ 

For each testcase, output in a single line answer, "Yes" if Chef can win the prize and "No" if not.

You may print each character of each string in uppercase or lowercase (for example, the strings "yEs", "yes", "Yes" and "YES" will all be treated as identical).

------ Constraints ------ 

$1 ≤ N, M ≤ 10^{5}$
$1 ≤ A_{i} ≤ M$
- Sum of $N$ over all tests is at most $10^{6}$
- Sum of $M$ over all tests is at most $10^{6}$

----- Sample Input 1 ------ 
3
4 4
1 2 3 4
5 4
4 2 1 1 1
4 4
4 4 4 4
----- Sample Output 1 ------ 
No
Yes
Yes
----- explanation 1 ------ 
TestCase 1: Since all the $4$ available topics have been taken up, Chef can't choose a distinct topic and hence can't win the prize. No one will win the prize this year.

TestCase 2: Since only $3$ distinct topics out of the $4$ available have been taken up, Chef can choose the remaining one, i.e, topic $3$ to win the prize jointly with the first and the second researcher.

TestCase 3: Since only $1$ distinct topic out of the $4$ available has been taken up, Chef can choose any of the remaining ones to win the prize.

Difficulty: EASY
Tags: Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
testcases = int(input())
while testcases:
	[N, M] = list(map(int, input().split()))
	topics = list(map(int, input().split()))
	num_set = set()
	for val in topics:
		num_set.add(val)
	req_sum = M * (M + 1) // 2
	curr_sum = 0
	for val in num_set:
		curr_sum += val
	if req_sum - curr_sum != 0:
		print('Yes')
	else:
		print('No')
	testcases -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	rese = [int(x) for x in input().split()]
	rese.sort()
	total = 1
	for i in range(1, n):
		if rese[i] != rese[i - 1]:
			total += 1
	if total < m:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	(N, M) = input().split()
	(N, M) = (int(N), int(M))
	A = list(map(int, input().split()))
	if len(set(A)) == M:
		print('No')
	else:
		print('Yes')


for i in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	c = set(l)
	if len(c) < b:
		print('Yes')
	else:
		print('No')


for i in range(int(input())):
	(m, n) = map(int, input().split())
	lst = list(map(int, input().split()))
	d = {}
	for i in lst:
		if i not in d.keys():
			d[i] = 1
		else:
			d[i] += 1
	ls = []
	for (k, v) in d.items():
		ls.append(k)
	if len(ls) < n:
		print('Yes')
	else:
		print('No')


for i in range(int(input())):
	(m, n) = map(int, input().split())
	a = list(map(int, input().split()))
	d = set(a)
	if len(d) < n:
		print('Yes')
	else:
		print('No')


for i in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	if b - len(d.keys()) > 0:
		print('Yes')
	else:
		print('No')


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	lst = list(map(int, input().split()))
	d = {}
	for i in lst:
		if i not in d.keys():
			d[i] = 1
		else:
			d[i] += 1
	if m - len(d.keys()) == 0:
		print('No')
	else:
		print('Yes')


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	k = set(l)
	if b - len(k) >= 1:
		print('Yes')
	else:
		print('No')


n = int(input())
for i in range(1, n + 1):
	d = {}
	(a, b) = map(int, input().split())
	lst = list(map(int, input().split()))
	l = list((i for i in range(1, b + 1)))
	for i in lst:
		if i not in d.keys():
			d[i] = 1
		else:
			d[i] += 1
	m = list(d.keys())
	if len(l) != len(m):
		print('Yes')
	else:
		print('No')


for i in range(int(input())):
	(m, n) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = set(l)
	if n - len(l1) >= 1:
		print('Yes')
	else:
		print('No')


t = int(input())
for i in range(t):
	(N, M) = map(int, input().split())
	li = list(map(int, input().split()))
	p = set(li)
	if len(p) == M:
		print('No')
	else:
		print('Yes')


def check(n, m, a):
	t = len(set(a))
	if t == m:
		return 'No'
	else:
		return 'Yes'
t = int(input())
l = []
for i in range(t):
	(n, m) = tuple(map(int, input().split()))
	a = list(map(int, input().split()))
	l.append(check(n, m, a))
for i in range(t):
	print(l[i])


for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	rs = list(map(int, input().split(' ')))
	s = list(range(1, m + 1))
	rs_lt = list(set(rs))
	if len(rs_lt) < len(s):
		print('Yes')
	else:
		print('No')


t = int(input())
for i in range(t):
	(N, M) = input().split()
	N = int(N)
	M = int(M)
	x = list(map(int, input().split()))
	y = set(x)
	if len(y) < M:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	l = set(a)
	if len(l) < m:
		print('Yes')
	else:
		print('No')


a = int(input(''))
for i in range(a):
	(N, M) = [int(x) for x in input('').split()]
	t = [int(x) for x in input('').split()]
	l = set(t)
	if len(l) < M:
		print('Yes')
	else:
		print('No')


t = int(input())
while t > 0:
	(a, b) = map(int, input().split())
	ls = list(map(int, input().split()))
	x = 0
	for i in set(ls):
		x += 1
	if x == b:
		print('No')
	else:
		print('Yes')
	t -= 1


T = int(input())
for tc in range(T):
	(N, M) = map(int, input().split(' '))
	l = list(map(int, input().split(' ')))
	s = set(l)
	if len(s) < M:
		print('Yes')
	else:
		print('No')


for i in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	l = list(range(1, m + 1))
	a = list(set(a))
	a.sort()
	if a == l:
		print('No')
	else:
		print('Yes')


t = int(input())
for i in range(t):
	flag = 0
	(n, m) = list(map(int, input().split()))
	a = set(map(int, input().split()))
	for j in range(1, m + 1):
		if j not in a:
			flag = 1
			break
	if flag == 1:
		print('Yes')
	else:
		print('No')


t = int(input())
for i in range(t):
	(N, M) = map(int, input().split())
	A = list(map(int, input().split()))
	unique = len(list(set(A)))
	if M == unique:
		print('No')
	else:
		print('Yes')


for t in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = set(a)
	if m != len(b):
		print('Yes')
	else:
		print('No')


for i in range(int(input())):
	(N, M) = map(int, input().split())
	A = [int(k) for k in input().split()]
	if M - len(set(A)) > 0:
		print('Yes')
	else:
		print('No')


T = int(input())
for i in range(T):
	(x, y) = map(int, input().split())
	lst = list(map(int, input().split()))
	ans = set(range(1, y + 1)) - set(lst)
	if len(ans) >= 1:
		print('Yes')
	else:
		print('No')


T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	b = list(dict.fromkeys(a))
	if len(b) == M:
		print('No')
	elif len(b) < M:
		print('Yes')


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	lis = list(map(int, input().split()))
	if len(set(lis)) < m:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 0
	a = set(a)
	for i in range(1, m + 1):
		if i not in a:
			c += 1
			break
	if c > 0:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lst = list(map(int, input().split()))
	s1 = set(lst)
	for i in range(m):
		if i + 1 not in s1:
			print('Yes')
			break
	else:
		print('No')


for i in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	d = {}
	ans = 0
	for i in l:
		if i not in d:
			d[i] = 1
	for i in range(1, m + 1):
		if i not in d:
			ans = 1
			print('Yes')
			break
	if ans == 0:
		print('No')


for i in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	s = sum(list(set(l)))
	if s == m * (m + 1) // 2:
		print('No')
	else:
		print('Yes')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = len(set(arr))
	if ans == m:
		print('No')
	else:
		print('Yes')