Aleksey has $n$ friends. He is also on a vacation right now, so he has $m$ days to play this new viral cooperative game! But since it's cooperative, Aleksey will need one teammate in each of these $m$ days.

On each of these days some friends will be available for playing, and all others will not. On each day Aleksey must choose one of his available friends to offer him playing the game (and they, of course, always agree). However, if any of them happens to be chosen strictly more than $\left\lceil\dfrac{m}{2}\right\rceil$ times, then all other friends are offended. Of course, Aleksey doesn't want to offend anyone.

Help him to choose teammates so that nobody is chosen strictly more than $\left\lceil\dfrac{m}{2}\right\rceil$ times.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10000$). Description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1\leq n, m\leq 100000$) standing for the number of friends and the number of days to play, respectively.

The $i$-th of the following $m$ lines contains an integer $k_i$ ($1\leq k_i\leq n$), followed by $k_i$ distinct integers $f_{i1}$, ..., $f_{ik_i}$ ($1\leq f_{ij}\leq n$), separated by spaces — indices of available friends on the day $i$.

It is guaranteed that the sums of $n$ and $m$ over all test cases do not exceed $100000$. It's guaranteed that the sum of all $k_i$ over all days of all test cases doesn't exceed $200000$.


-----Output-----

Print an answer for each test case. If there is no way to achieve the goal, print "NO".

Otherwise, in the first line print "YES", and in the second line print $m$ space separated integers $c_1$, ..., $c_m$. Each $c_i$ must denote the chosen friend on day $i$ (and therefore must be one of $f_{ij}$).

No value must occur more than $\left\lceil\dfrac{m}{2}\right\rceil$ times. If there is more than one possible answer, print any of them.


-----Examples-----

Input
2
4 6
1 1
2 1 2
3 1 2 3
4 1 2 3 4
2 2 3
1 3
2 2
1 1
1 1
Output
YES
1 2 1 1 2 3 
NO


-----Note-----

None

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

Complete search

Implementation

Constructive algorithms
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	days = []
	ans = []
	for i in range(m):
		days.append(list(map(int, input().split())))
		ans.append(days[i][1])
	freq = {}
	for num in ans:
		if num in freq:
			freq[num] += 1
		else:
			freq[num] = 1
	f = max(freq.keys(), key=lambda k: freq[k])
	z = freq[f]
	if z <= (m + 1) // 2:
		print('YES')
		print(*ans)
	else:
		for i in range(m):
			if ans[i] == f:
				if days[i][0] > 1:
					z -= 1
					ans[i] = days[i][2]
			if z <= (m + 1) // 2:
				break
		else:
			print('NO')
			continue
		print('YES')
		print(*ans)


import sys
from math import ceil
for _ in range(int(sys.stdin.readline())):
	(n, m) = map(int, sys.stdin.readline().split())
	date = []
	friends = [0] * (n + 1)
	ans = [0] * m
	limit = ceil(m / 2)
	for i in range(m):
		temp = list(map(int, sys.stdin.readline().split()))
		date.append(temp[1:])
		if temp[0] == 1:
			friends[temp[1]] += 1
			ans[i] = temp[1]
			continue
	if max(friends) > limit:
		print('NO')
		continue
	for i in range(m):
		if ans[i] != 0:
			continue
		for j in range(len(date[i])):
			if friends[date[i][j]] < limit:
				friends[date[i][j]] += 1
				ans[i] = date[i][j]
				break
	print('YES')
	print(*ans)


import math

def solve():
	(n, m) = map(int, input().split())
	maxi = math.ceil(m / 2)
	A = [[] for _ in range(m)]
	for i in range(m):
		(k, *A[i]) = map(int, input().split())
	ans = list()
	cnt = dict()
	f = -1
	for i in range(m):
		ff = A[i][0]
		ans.append(ff)
		cnt[ff] = cnt.get(ff, 0) + 1
		if cnt[ff] > maxi:
			f = ff
	for i in range(m):
		if f != -1 and cnt[f] > maxi and (len(A[i]) > 1) and (f == A[i][0]):
			cnt[f] = cnt[f] - 1
			ans[i] = A[i][1]
	if cnt.get(f, 0) <= maxi:
		print('YES\n', *ans)
	else:
		print('NO')
T = int(input())
for _ in range(T):
	solve()


from collections import Counter
t = int(input())

def main():
	(n, m) = [int(s) for s in input().split()]
	c = Counter()
	res = [0] * m
	arr = []
	for i in range(m):
		l = [int(s) for (i, s) in enumerate(input().split()) if i > 0]
		arr.append(l)
		if len(l) == 1:
			c[l[0]] += 1
			res[i] = l[0]
	for value in c.values():
		if value > (m + 1) // 2:
			print('NO')
			return
	for i in range(m):
		if res[i] == 0:
			if c[arr[i][0]] < c[arr[i][1]]:
				res[i] = arr[i][0]
				c[arr[i][0]] += 1
			else:
				res[i] = arr[i][1]
				c[arr[i][1]] += 1
	print('YES')
	print(' '.join([str(e) for e in res]))
for _ in range(t):
	main()


from collections import defaultdict
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	p = (m + 1) // 2
	k = defaultdict(int)
	ans = [0] * m
	gh = [(i, list(map(int, input().split(' ')))[1:]) for i in range(0, m)]
	flag = 0
	gh.sort(key=lambda day: len(day[1]))
	for (i, day) in gh:
		for v in day:
			if k[v] + 1 <= p:
				ans[i] = v
				k[v] += 1
				break
		else:
			print('NO')
			break
	else:
		print('YES')
		print(*ans)


import math

def f(lst, n, m):
	selection = [0 for _ in range(m)]
	d = dict()
	for i in range(1, n + 1):
		d[i] = 0
	for i in range(m):
		friend = lst[i][1]
		d[friend] += 1
		selection[i] = friend
	overflow = -1
	for (x, y) in d.items():
		if y > math.ceil(m / 2):
			overflow = x
	if overflow == -1:
		print('YES')
		for i in range(m):
			print(selection[i], end=' ')
		print()
	else:
		for i in range(m):
			if d[overflow] <= math.ceil(m / 2):
				break
			if lst[i][1] == overflow and lst[i][0] > 1:
				d[overflow] -= 1
				d[lst[i][2]] += 1
				selection[i] = lst[i][2]
		if d[overflow] <= math.ceil(m / 2):
			print('YES')
			for i in range(m):
				print(selection[i], end=' ')
			print()
		else:
			print('NO')
	return
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	lst = []
	for _ in range(m):
		lst.append(list(map(int, input().split())))
	f(lst, n, m)


import math
t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split()]
	ks = []
	fs = []
	res = [-1 for j in range(m)]
	counts = [0 for j in range(n)]
	impossible = False
	for j in range(m):
		kf = [int(x) for x in input().split()]
		ks.append(kf[0])
		fs.append(kf[1:])
		if kf[0] == 1:
			res[j] = kf[1]
			counts[kf[1] - 1] += 1
			if counts[kf[1] - 1] > math.ceil(m / 2):
				impossible = True
	if not impossible:
		for j in range(m):
			if res[j] == -1:
				stopped = False
				for f in fs[j]:
					if counts[f - 1] < math.ceil(m / 2):
						res[j] = f
						counts[f - 1] += 1
						stopped = True
						break
				if not stopped:
					impossible = True
					break
	if impossible:
		print('NO')
	else:
		print('YES')
		print(' '.join([str(x) for x in res]))


import math
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	allNums = []
	solution = [-1 for _ in range(m)]
	counts = [0 for _ in range(n + 10)]
	boundary = int(math.ceil(m / 2))
	works = True
	for i in range(m):
		nums = list(map(int, input().split()))
		nums = nums[1:]
		allNums.append(nums)
		if len(nums) == 1:
			solution[i] = nums[0]
			counts[nums[0]] += 1
			if counts[nums[0]] > boundary:
				works = False
	if not works:
		print('NO')
		continue
	for i in range(len(solution)):
		x = solution[i]
		if x == -1:
			cur = allNums[i]
			for y in cur:
				if counts[y] < boundary:
					counts[y] += 1
					solution[i] = y
					break
	print('YES')
	print(*solution)


from collections import defaultdict
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = defaultdict(int)
	days = [(i, list(map(int, input().split()))[1:]) for i in range(m)]
	days.sort(key=lambda day: len(day[1]))
	ans = [0] * m
	for (i, day) in days:
		for values in day:
			if d[values] + 1 <= (m + 1) // 2:
				ans[i] = values
				d[values] += 1
				break
		else:
			print('NO')
			break
	else:
		print('YES')
		print(*ans)


rn = lambda : int(input())
rns = lambda : map(int, input().split())
rl = lambda : list(map(int, input().split()))
rs = lambda : input()
YN = lambda x: print('YES') if x else print('NO')
mod = 10 ** 9 + 7
from collections import Counter
from math import ceil
for _ in range(rn()):
	(n, m) = rns()
	days = []
	ans = []
	for i in range(m):
		days.append(rl()[1:])
		ans.append(days[-1][0])
	c = Counter(ans)
	flag = True
	for num in c:
		if c[num] > ceil(m / 2):
			for i in range(m):
				if ans[i] == num and len(days[i]) > 1:
					ans[i] = days[i][1]
					c[num] -= 1
					if c[num] == ceil(m / 2):
						break
			if c[num] > ceil(m / 2):
				flag = False
			break
	if flag:
		print('YES')
		print(*ans)
	else:
		print('NO')


import collections
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	f = [list(map(int, input().split()))[1:] for _ in range(m)]
	cnts = collections.Counter()
	df = [0 for _ in range(m)]
	relax = None
	mid = (m + 1) // 2
	for i in range(m):
		df[i] = f[i][0] - 1
		cnts[df[i]] += 1
		if cnts[df[i]] > mid:
			relax = df[i]
	if relax is not None:
		for i in range(m):
			if cnts[relax] <= mid:
				break
			if df[i] == relax:
				if len(f[i]) > 1:
					cnts[df[i]] -= 1
					df[i] = f[i][1] - 1
					cnts[df[i]] += 1
	if relax is not None and cnts[relax] > mid:
		print('NO')
	else:
		print('YES')
		print(*[x + 1 for x in df], sep=' ')


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	mat = []
	for __ in range(m):
		l = list(map(int, input().split()))
		mat.append(l)
	d = [0] * m
	flag = 0
	f = [0] * (n + 1)
	mx = (m + 1) // 2
	for i in range(m):
		if mat[i][0] == 1:
			d[i] = mat[i][1]
			f[mat[i][1]] += 1
			if f[mat[i][1]] > mx:
				flag = 1
				break
	if flag == 1:
		print('NO')
	else:
		print('YES')
		for i in range(m):
			if d[i] != 0:
				print(d[i], end=' ')
			else:
				g = 0
				for j in range(1, mat[i][0] + 1):
					if g == 1:
						break
					if f[mat[i][j]] < mx:
						f[mat[i][j]] += 1
						print(mat[i][j], end=' ')
						g = 1
		print()


from collections import defaultdict
from math import ceil
for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	(lst, ans, Counter) = ([], [0] * m, defaultdict(int))
	pointer = []
	for xx in range(m):
		temp = list(map(int, input().split(' ')))
		lst.append(temp[1:])
		pointer.append(xx)
	pointer.sort(key=lambda x: len(lst[x]))
	lst.sort(key=lambda x: len(x))
	for i in range(m):
		for val in lst[i]:
			if Counter[val] < ceil(m / 2):
				Counter[val] += 1
				ans[pointer[i]] = val
				break
	if min(ans) == 0:
		print('NO')
	else:
		print('YES')
		print(*ans)


def solve(M, n, m):
	I = {}
	S = {}
	result = [0] * m
	for i in range(m):
		k = M[i][0]
		for j in range(1, k + 1):
			I[M[i][j]] = I.get(M[i][j], 0) + 1
		if k == 1:
			S[M[i][1]] = S.get(M[i][1], 0) + 1
			result[i] = M[i][1]
	maxFreq = (m + 1) // 2
	for (k, f) in S.items():
		if f > maxFreq:
			return ['NO']
	A = {}
	for (k, f) in I.items():
		A[k] = min(f, maxFreq) - S.get(k, 0)
	for i in range(m):
		if result[i] > 0:
			continue
		for j in range(1, M[i][0] + 1):
			if A[M[i][j]] > 0:
				result[i] = M[i][j]
				A[M[i][j]] -= 1
				break
	return ['YES', result]
t = int(input())
for tc in range(t):
	(n, m) = map(int, input().split())
	M = []
	for i in range(m):
		M.append(list(map(int, input().split())))
	result = solve(M, n, m)
	print(result[0])
	if len(result) > 1:
		print(*result[1])


import collections
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = collections.defaultdict(int)
	(day, v) = ({}, True)
	k = (m + 1) // 2
	for i in range(m):
		l = list(map(int, input().split()))
		day[i] = l[1:]
	day = sorted(day.items(), key=lambda x: len(x[1]))
	ans = [0] * m
	for items in day:
		c = 0
		for j in items[1]:
			if d[j] + 1 <= k:
				ans[items[0]] = j
				d[j] += 1
				c = 1
				break
		if c == 0:
			v = False
			break
	if v == False:
		print('NO')
	else:
		print('YES')
		print(*ans)


ll = lambda : map(int, input().split())
t = lambda : int(input())
ss = lambda : input()
lx = lambda x: map(int, input().split(x))
from math import log10, log2, ceil, factorial as f, gcd

def f(k1, k2):
	return min(k1, k2) + (max(k1, k2) - min(k1, k2)) // 2
for _ in range(t()):
	(n, m) = ll()
	d = {}
	count = [0] * (n + 1)
	arr = [0] * m
	days = {}
	for i in range(m):
		l = list(ll())
		k = l[0]
		l = l[1:]
		if k == 1 and count[l[0]] + 1 <= ceil(m / 2):
			arr[i] = l[0]
			count[l[0]] += 1
		for j in l:
			if j not in d:
				d[j] = []
			d[j].append(i)
	for j in d.keys():
		for x in d[j]:
			if count[j] + 1 <= ceil(m / 2):
				if arr[x] == 0:
					arr[x] = j
					count[j] += 1
			else:
				break
	if 0 in arr:
		print('NO')
	else:
		print('YES')
		print(*arr)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	f = []
	tot = [0] * n
	uni = [0] * n
	pop = 0
	popind = -1
	threshold = (m + 1) // 2
	for j in range(m):
		f.append(input().split())
		for k in range(len(f[j])):
			cur = int(f[j][k])
			f[j][k] = cur
			if k > 0:
				tot[cur - 1] += 1
				if tot[cur - 1] > pop:
					pop = tot[cur - 1]
					popind = cur
				if len(f[j]) == 2:
					uni[cur - 1] += 1
	if uni[popind - 1] > threshold:
		print('NO')
	else:
		print('YES')
		already = 0
		answer = ''
		for j in range(m):
			f[j][0] = -1
			if len(f[j]) == 2:
				answer += str(f[j][1])
			elif popind in f[j]:
				if already == threshold - uni[popind - 1]:
					if f[j][1] == popind:
						answer += str(f[j][2])
					else:
						answer += str(f[j][1])
				else:
					answer += str(popind)
					already += 1
			else:
				answer += str(f[j][1])
			if j != m:
				answer += ' '
		print(answer)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	f = [m // 2 + m % 2 for i in range(n)]
	ans = 'YES'
	a = []
	fl = [None] * m
	for i in range(m):
		a.append(([int(i) for i in input().split()], i))
	a.sort()
	for i in range(m):
		for j in a[i][0][1:]:
			if f[j - 1]:
				fl[a[i][1]] = j
				f[j - 1] -= 1
				break
		else:
			ans = 'NO'
	print(ans)
	if ans == 'YES':
		print(*fl)


from operator import itemgetter
t = int(input())
for _ in range(t):
	(n, m) = (int(el) for el in input().split())
	all_k_2d_list = list()
	for ki in range(m):
		(k_size, *k_list) = [int(k) for k in input().split()]
		all_k_2d_list.append(k_list + [ki])
	counter = dict.fromkeys(range(1, n + 1), 0)
	all_k_2d_list.sort(key=len)
	not_available_k_set = set()
	results_list = []
	YES_res = True
	for k_list in all_k_2d_list:
		res = None
		(*k_list, day_i) = k_list
		k_list = tuple(set(k_list) - not_available_k_set)
		for k in k_list:
			counter[k] += 1
			if counter[k] > (m + 1) // 2:
				not_available_k_set.add(k)
			else:
				res = (k, day_i)
				break
		if res is None:
			YES_res = False
			break
		results_list.append(res)
	if YES_res:
		print('YES')
		results_list.sort(key=itemgetter(-1))
		print(*map(itemgetter(0), results_list))
	else:
		print('NO')


for i in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	b = [m // 2 + m % 2 for i in range(n)]
	ans = 'YES'
	res = [0 for i in range(m)]
	a = sorted([([int(i) for i in input().split()], i) for i in range(m)])
	for i in range(m):
		for j in a[i][0][1:]:
			if b[j - 1]:
				res[a[i][1]] = j
				b[j - 1] -= 1
				break
		else:
			ans = 'NO'
	print(ans)
	if ans == 'YES':
		print(*res)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	f = [m // 2 + m % 2 for i in range(n)]
	answer = 'YES'
	a = []
	available = [None] * m
	for i in range(m):
		a.append(([int(i) for i in input().split()], i))
	a.sort()
	for i in range(m):
		for j in a[i][0][1:]:
			if f[j - 1]:
				available[a[i][1]] = j
				f[j - 1] -= 1
				break
		else:
			answer = 'NO'
	print(answer)
	if answer == 'YES':
		print(*available)


from math import ceil
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	MAX = ceil(m / 2)
	dd = {i: [] for i in range(1, n + 1)}
	p = []
	for i in range(m):
		t = list(map(int, input().split()))
		uz = t[0]
		p.append(set())
		for a in range(1, uz + 1):
			el = t[a]
			dd[el].append(i)
			p[-1].add(el)
	for i in dd:
		el = dd[i]
		c = []
		for a in el:
			le = len(p[a])
			c.append((le, a))
		c.sort(reverse=True)
		for a in range(len(c) - MAX):
			(tek, ind) = c[a]
			p[ind].remove(i)
	ans = []
	f = True
	for i in p:
		if len(i) == 0:
			f = False
			print('NO')
			break
		else:
			ans.append(next(iter(i)))
	if f:
		print('YES')
		print(*ans)


tc = int(input())
while tc > 0:
	(n, m) = map(int, input().strip().split())
	(vv, ans, tmp) = ([], [], [])
	for i in range(n + 9):
		empt = []
		ans.append(empt)
	for i in range(m):
		aa = list(map(int, input().strip().split()))
		x = aa[0]
		tmp.append((x, i))
		a = []
		for j in range(1, x + 1):
			v = aa[j]
			a.append(v - 1)
		vv.append(a)
	tmp.sort()
	k = (m + 1) // 2
	for i in range(m):
		d = tmp[i][1]
		sz = tmp[i][0]
		for j in range(sz):
			u = vv[d][j]
			if len(ans[u]) < k:
				ans[u].append(d)
				break
	day = [-1 for i in range(m + 9)]
	for i in range(n):
		for j in range(len(ans[i])):
			d = ans[i][j]
			day[d] = i
	flag = True
	for i in range(m):
		if day[i] == -1:
			flag = False
	if flag == False:
		print('NO')
	else:
		print('YES')
		for i in range(m):
			print(day[i] + 1, end=' ')
		print()
	tc -= 1