Basic Diplomacy (Codeforces 1484C)
Tags: Greedy, flows

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 10\,000$$$). Description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\leq n, m\leq 100\,000$$$) 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 $$$100\,000$$$. It's guaranteed that the sum of all $$$k_i$$$ over all days of all test cases doesn't exceed $$$200\,000$$$.

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.


Sample Inputs:
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

Sample Outputs:
YES
1 2 1 1 2 3 
NO

Solution (Python):
from collections import defaultdict
import math

def solve(friends):
    num_days = len(friends)
    max_limit = math.ceil(num_days / 2)
    max_counter_hash = defaultdict(int)
    max_counter = 1
    max_friend = friends[0][0]
    for friends_of_day in friends:
        for friend in friends_of_day:
            max_counter_hash[friend] += 1
            if max_counter_hash[friend] > max_counter:
                max_counter = max_counter_hash[friend]
                max_friend = friend
    max_friend_used_count = 0
    for i in range(num_days):
        if len(friends[i]) == 1 and friends[i][0] == max_friend:
            max_friend_used_count += 1
    result = []
    for i in range(num_days):
        if len(friends[i]) == 1:
            result.append(friends[i][0])
        elif max_friend in friends[i] and max_friend_used_count < max_limit:
            result.append(max_friend)
            max_friend_used_count += 1
        else:
            for friend in friends[i]:
                if friend != max_friend:
                    result.append(friend)
                    break
    friend_used_counter_hash = defaultdict(int)
    for friend in result:
        friend_used_counter_hash[friend] += 1
        if friend_used_counter_hash[friend] > max_limit:
            return 'NO'
    return 'YES\n' + ' '.join(result)

def run():
    t = int(input())
    for i in range(t):
        (num_friends, num_days) = map(int, input().split())
        friends = []
        for day in range(num_days):
            (_, *available_friends) = input().split()
            friends.append(available_friends)
        print(solve(friends))
run()

Solution (Python):
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)

Solution (Python):
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)