Alice and Bob went to a pet store. There are N animals in the store where the i^{th} animal is of type A_{i}.

Alice decides to buy some of these N animals. Bob decides that he will buy all the animals left in the store after Alice has made the purchase.

Find out whether it is possible that Alice and Bob end up with exactly same [multiset] of animals. 

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains an integer N — the number of animals in the store.
- The next line contains N space separated integers, denoting the type of each animal.

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

For each test case, output on a new line, YES, if it is possible that Alice and Bob end up with exactly same multiset of animals and NO otherwise.

You may print each character in uppercase or lowercase. For example, the strings YES, yes, Yes, and yES are considered identical.

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 100$
- The sum of $N$ over all test cases won't exceed $2\cdot 10^{5}$.

----- Sample Input 1 ------ 
4
3
4 4 4
4
2 3 3 2
4
1 2 2 3
6
5 5 1 5 1 5

----- Sample Output 1 ------ 
NO
YES
NO
YES

----- explanation 1 ------ 
Test case $1$: There are $4$ possible cases:
- Alice does not buy anything: Bob will buy all the animals and will have $3$ animals of type $4$.
- Alice buys $1$ animal of type $4$: Bob will buy the remaining two animals of type $4$.
- Alice buys $2$ animals of type $4$: Bob will buy the remaining one animal of type $4$.
- Alice buys all $3$ animals of type $4$: Bob will not buy anything.

In no case, both Alice and Bob can have the exactly same multiset of pets.

Test case $2$: If Alice buys animals $1$ and $2$, having types $2$ and $3$ respectively, Bob will buy animals $3$ and $4$, having types $3$ and $2$ respectively. Thus, both Alice and Bob have $1$ animal of type $2$ and $1$ animal of type $3$.

Test case $3$: It can be proven that Alice and Bob cannot have the same multiset of pets in any case.

Test case $4$: If Alice buys animals $1, 2, $ and $5$, having types $5, 5,$ and $1$ respectively, Bob will buy animals $3, 4,$ and $6$, having types $1, 5,$ and $5$ respectively. Thus, both Alice and Bob have $1$ animal of type $1$ and $2$ animals of type $5$.

Source: codechef | Difficulty: EASY
Tags: Sorting

Data structures


Solutions:
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	k = set(a)
	f = 0
	for i in k:
		if a.count(i) % 2:
			f = 1
	if f == 1:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = set(l)
	f = 0
	for i in s:
		if l.count(i) % 2:
			f = 1
	if f == 1:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	s = set(x)
	for i in s:
		if x.count(i) % 2 != 0:
			print('NO')
			break
	else:
		print('YES')


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	c = Counter(input().split())
	print('YES' if all([x % 2 == 0 for (k, x) in c.items()]) else 'NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = set(l)
	flag = 0
	for i in a:
		if l.count(i) % 2 == 1:
			flag = 1
	if flag:
		print('NO')
	else:
		print('YES')


from collections import Counter as C
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = C(l)
	f = 1
	for i in d:
		if d[i] & 1:
			f = 0
			break
	print('YES') if f else print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = set(l)
	count = 0
	for i in s:
		a = l.count(i)
		if a % 2 == 0:
			count = count + 1
	if len(s) == count:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = set(a)
	p = 0
	for i in m:
		if a.count(i) % 2 != 0:
			p = 1
	if p == 1:
		print('NO')
	else:
		print('YES')


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	i1 = 0
	if n % 2 != 0:
		print('NO')
	else:
		b = set(a)
		for i in b:
			c = a.count(i)
			if c % 2 != 0:
				print('NO')
				break
			else:
				i1 += 1
		if i1 == len(b):
			print('YES')


t = int(input())
while t > 0:
	n = int(input())
	a = input().split()
	sa = set(a)
	c = 1
	for i in sa:
		if a.count(i) % 2 != 0:
			c = 0
			break
	if c == 1:
		print('YES')
	else:
		print('NO')
	t -= 1


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = set(l)
	flag = 0
	for i in s:
		if l.count(i) % 2 != 0:
			flag = 10
	if flag == 10:
		print('NO')
	else:
		print('YES')


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = Counter(l).items()
	v = Counter(l).values()
	count = 0
	for i in v:
		if i % 2 != 0:
			count += 1
		else:
			pass
	if count == 0:
		print('YES')
	else:
		print('NO')


def possibility(l):
	if len(l) % 2 != 0:
		return 'NO'
	else:
		v = []
		dict1 = {}
		for i in l:
			if i not in dict1:
				dict1[i] = 1
			else:
				dict1[i] += 1
		for i in dict1:
			if dict1[i] % 2 != 0:
				return 'NO'
	return 'YES'
n = int(input())
for i in range(n):
	x = int(input())
	l = list(map(int, input().split()))
	print(possibility(l))


for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	d = {}
	for i in a:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	c = 0
	for i in d:
		if d[i] % 2 != 0:
			c = 1
			break
	if c == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n1 = int(input())
	s1 = list(map(int, input().split()))
	d = {}
	for i in s1:
		if i not in d.keys():
			d[i] = 1
		else:
			d[i] += 1
	flag = 1
	for i in d.keys():
		if d[i] % 2 != 0:
			flag = 0
			break
	if flag == 0:
		print('NO')
	else:
		print('YES')


from collections import Counter as Cn
T = int(input())
for i in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	l = Cn(arr)
	f = 1
	for i in l:
		if l[i] & 1:
			f = 0
			break
	print('YES') if f else print('NO')


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	c = Counter(arr)
	for i in c.values():
		if i % 2 != 0:
			print('NO')
			break
	else:
		print('YES')


from collections import Counter
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count = 1
	s = Counter(a)
	for j in s:
		if s[j] % 2 != 0:
			count = 0
			break
		else:
			continue
	print('YES') if count == 1 else print('NO')


for i in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	x1 = set(x)
	for j in x1:
		if x.count(j) % 2 != 0:
			print('NO')
			break
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = set(a)
	x = 0
	for i in b:
		if a.count(i) % 2 == 1:
			x = x + 1
	if x > 0:
		print('NO')
	else:
		print('YES')


def same_multiset(n, animals):
	count = {}
	for animal in animals:
		count[animal] = count.get(animal, 0) + 1
	for freq in count.values():
		if freq % 2 != 0:
			return 'NO'
	return 'YES'
t = int(input())
for _ in range(t):
	n = int(input())
	animals = list(map(int, input().split()))
	result = same_multiset(n, animals)
	print(result)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in a:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	if len(a) % 2 == 0:
		flg = 1
		for key in d:
			if d[key] % 2 != 0:
				flg = 0
				print('NO')
				break
			else:
				flg = 1
		if flg == 1:
			print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	arr = input().split(' ')
	if n % 2 != 0:
		print('NO')
		continue
	cnt = {}
	for i in arr:
		if i in cnt:
			cnt[i] += 1
		else:
			cnt[i] = 1
	check = True
	for i in cnt:
		if cnt[i] % 2 != 0:
			print('NO')
			check = False
			break
	if check:
		print('YES')


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	cnt = Counter(arr)
	flag = 0
	if n % 2:
		flag = 1
	else:
		for (i, j) in cnt.items():
			if j % 2:
				flag = 1
				break
	if flag == 0:
		print('YES')
	else:
		print('NO')


from collections import Counter
n = int(input())
for i in range(n):
	k = int(input())
	l = list(map(int, input().split()))
	ans = Counter(l)
	flag = True
	for i in ans:
		if ans[i] % 2 != 0:
			flag = False
			break
	if flag:
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	x = int(input())
	p = 0
	a = list(map(int, input().split()))
	fc = [0] * (max(a) + 1)
	for i in range(len(a)):
		fc[a[i]] += 1
	for i in range(len(fc)):
		if fc[i] % 2 != 0:
			print('NO')
			p = 1
			break
	if p == 0:
		print('YES')


from collections import Counter as cn
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = cn(a)
	f = 1
	for i in d:
		if d[i] & 1:
			f = 0
			break
	print('YES' if f else 'NO')


T = int(input())
for t in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	D = {}
	for a in A:
		if a in D:
			D[a] += 1
		else:
			D[a] = 1
	result = 'YES'
	for (k, a) in enumerate(A):
		if D[a] % 2 == 0:
			continue
		else:
			result = 'NO'
			break
	print(result)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a1 = set(a)
	flag = True
	for i in a1:
		if a.count(i) % 2 != 0:
			flag = False
			print('NO')
			break
	if flag == True:
		print('YES')


n = int(input())
for i in range(n):
	m = int(input())
	b = list(map(int, input().split()))
	t = list(set(b))
	o = []
	for j in t:
		if b.count(j) % 2 == 0:
			o.append(j)
	if o == t:
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	k = int(input())
	s = list(map(int, input().split()))
	r = set(s)
	flag = 0
	for i in r:
		if s.count(i) % 2 != 0:
			flag = 1
	if flag == 1:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	b = set(A)
	c = list(b)
	flag = 0
	for i in c:
		if A.count(i) % 2 == 0:
			flag = 1
		else:
			flag = 0
			break
	if flag == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	s = set(l)
	for i in s:
		if l.count(i) % 2 != 0:
			print('NO')
			break
	else:
		print('YES')


for i in range(int(input())):
	x = int(input())
	y = list(map(int, input().split()))
	y.sort()
	c = []
	d = []
	h = 0
	for i in range(x):
		if i % 2 == 0:
			c.append(y[i])
		else:
			d.append(y[i])
	if c == d:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	b.sort()
	c = []
	d = []
	for i in range(0, a):
		if i % 2 == 0:
			c.append(b[i])
		else:
			d.append(b[i])
	if c == d:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	a = int(input())
	l = list(map(int, input().split()))
	(d, c) = ({}, 0)
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	for (keys, values) in d.items():
		if d[keys] % 2 == 1:
			c += 1
	if c >= 1:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(0, t):
	n = int(input())
	s = list(map(int, input().split()))
	if n % 2 != 0:
		print('NO')
	else:
		c = 0
		f = [0] * (max(s) + 1)
		for k in s:
			ind = k
			f[ind] = f[ind] + 1
		for j in range(1, len(f)):
			if f[j] % 2 != 0:
				c = c + 1
				break
		if c == 1:
			print('NO')
		else:
			print('YES')


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = set(a)
	l = []
	for h in s:
		l.append(a.count(h))
	for j in range(len(l)):
		if l[j] % 2 != 0:
			print('NO')
			break
	else:
		print('YES')


for _ in range(int(input())):
	x = int(input())
	List = list(map(int, input().split()))
	l = []
	List2 = []
	c = 0
	for i in List:
		if i not in l:
			l.append(i)
	for i in l:
		q = List.count(i)
		List2.append(q)
	for i in List2:
		if i % 2 == 0:
			c += 1
	if c == len(List2):
		print('YES')
	else:
		print('NO')


x = int(input())
vxz = []
for un in range(0, x):
	b = int(input())
	vx = str(input())
	iir = vx.split(' ')
	f = []
	for nn in iir:
		f.append(int(nn))
	vxz.append(f)
for ttbc in vxz:
	gbt = {}
	for tew in ttbc:
		if tew not in gbt.keys():
			gbt[tew] = 1
		else:
			gbt[tew] += 1
	ans = 'YES'
	for yyhf in gbt.keys():
		if gbt[yyhf] % 2 == 0:
			continue
		else:
			ans = 'NO'
			break
	print(ans)