1484C - Basic Diplomacy - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
/* 142857 cyclic number 0588235294117647 cyclic number */
#define ll long long
#define mk make_pair
#define vvll(n, m, v) vector<vector<ll>> v(n, vll(m, 0))
#define all(v) v.begin(), v.end()
#define vvc vector<vector<char>>
#define vss vector<string>
#define emp emplace
#define pb push_back
#define pf push_front
#define dq deque
#define llmn LONG_LONG_MIN
#define llmx LONG_LONG_MAX
#define umll unordered_map<ll>
#define mll map<ll, ll>
#define sll set<ll>
#define usll unordered_set<ll>
#define vll vector<ll>
#define vpll vector<pair<ll, ll>>
#define pll pair<ll, ll>
#define mk make_pair
#define ss string
#define pqmin priority_queue<ll, vll, greater<ll>()>
#define pqmax priority_queue<ll>
#define llmin LONG_LONG_MIN
#define llmax LONG_LONG_MAX
#define s second
#define f first
#define repg(i, a, b, c) for (ll i = a; i < b; i += c)
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define rrep(i, a, b) for (ll i = a; i > b; i--)
#define rrepg(i, a, b, c) for (ll i = a; i > b; i -= c)
#define trv(it, mp) for (auto it : mp)
#define rot_l(v, p) rotate(v.begin(), v.begin() + p, v.end())
#define rot_r(v, p) rotate(v.begin(), v.begin() + v.size() - p, v.end())
#define cont(v, p) count(v.begin(), v.end(), p)
#define accumulate(v, k) accumulate(v[i].begin(), v[i].begin() + k, 0)
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);
const ll M = 1e9 + 7;
const ll M2 = 998244353;
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define setIntersection(d1, d2, cd) set_intersection(d1.begin(), d1.end(), d2.begin(), d2.end(), inserter(cd, cd.begin()));

ll mod(ll x)
{
    return ((x % M + M) % M);
}
ll add(ll a, ll b)
{
    return mod(mod(a) + mod(b));
}
ll mul(ll a, ll b)
{
    return mod(mod(a) * mod(b));
}
ll Floor(ll x, ll a)
{
    if (x < 0)
    {
        return floor(x / a) - 1;
    }
    return floor(x / a);
}

/*-----------------Number_Theory---------------------------------------------------*/
ll fac[2000];
signed binExp(ll a, ll b, ll m)
{
    ll ans = 1;
    while (b > 0)
    {
        if (b & 1)
        {
            ans = (ans * a) % m;
            b = b - 1;
        }
        a = (a * a) % m;
        b = b >> 1;
    }
    return ans % m;
}
void fact(ll n)
{
    fac[0] = 1;
    rep(i, 1, n + 1) fac[i] = (i * fac[i - 1]) % M;
    return;
}
ll ncr(ll n, ll r)
{
    if (r > n)
        return 0;
    return ((fac[n] * binExp(fac[n - r], M - 2, M)) % M * binExp(fac[r], M - 2, M)) % M;
}
ll gcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll x1, y1;
    ll d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

vector<pair<int, int>> factors;
void getFactors(int n)
{
    factors.clear();
    int d = 1;
    for (int i = 2; i * i <= n; i += d, d = 2)
        if (n % i == 0)
        {
            factors.push_back(make_pair(i, 0));
            while (n % i == 0)
            {
                n /= i;
                factors.back().second++;
            }
        }
    if (n != 1)
        factors.push_back(make_pair(n, 1));
}

vector<int> divisors;
void getDivisors(int ind = 0, int res = 1)
{
    if (ind == (int)factors.size())
    {
        divisors.push_back(res);
        return;
    }
    for (int i = 0; i <= factors[ind].second; i++)
    {
        getDivisors(ind + 1, res);
        res *= factors[ind].first;
    }
}
/*----------------------------Number_Theory_End----------------------------------------------*/
bool check(ll mid)
{
}
ll bin_Search(ll l, ll r, ll ans)
{
    while (l <= r)
    {
        ll mid = (l + r) >> 1;
        if (check(mid))
        {
            l = mid;
            ans = mid;
        }
        else
        {
            r = mid;
        }
    }
    return ans;
}
ll lcm(ll a, ll b)
{
    return (a * b) / (__gcd(a, b));
}
bool is_Palindrom(string s)
{
    string z = s;
    reverse(s.begin(), s.end());
    return s == z;
}
ll lis(vll &v)
{
    ll size = v.size();
    vll temp;
    temp.push_back(v[0]);
    ll len = 1;
    rep(i, 1, size)
    {
        if (temp.back() < v[i])
        {
            temp.push_back(v[i]);
            len++;
        }
        else
        {
            ll ind = lower_bound(all(temp), v[i]) - temp.begin();
            temp[ind] = v[i];
        }
    }
    return len;
}

ll di[] = {-1, 0, 0, 1};
ll dj[] = {0, -1, 1, 0};

vll vis;
vll dis;
vll par;
vector<vll> adj;
vector<vpll> adj_w;
vll pathvis;
stack<ll> topoStack;
vll topo;
vll indegree;
vector<vector<ll>> adj_matrix;

class DisjointSet
{
    // no. of component -----> parent[node]==node
    // detect no. of usless edges
public:
    vll rank, size, parent;
    DisjointSet(ll n)
    {
        rank.resize(n + 1, 0);
        size.resize(n + 1, 1);
        parent.resize(n + 1, 0);
        rep(i, 0, n + 1)
        {
            parent[i] = i;
        }
    }
    ll findUPar(ll node)
    {
        if (node == parent[node])
        {
            return node;
        }
        return parent[node] = findUPar(parent[node]);
    }
    void unionByRank(ll u, ll v)
    {

        // pathCompression
        ll par_ult_v = findUPar(v);
        ll par_ult_u = findUPar(u);

        if (par_ult_u == par_ult_v)
        {
            return;
        }
        // add smaller to larger
        if (rank[par_ult_u] < rank[par_ult_v])
        {
            parent[par_ult_u] = par_ult_v;
        }
        else if (rank[par_ult_v] < rank[par_ult_u])
        {

            parent[par_ult_v] = par_ult_u;
        }
        else
        {
            parent[par_ult_v] = par_ult_u;
            rank[par_ult_u]++;
        }
        return;
    }
    void unionBySize(ll u, ll v)
    {
        ll par_ult_v = findUPar(v);
        ll par_ult_u = findUPar(u);

        if (par_ult_u == par_ult_v)
        {
            return;
        }
        // add smaller to larger
        if (size[par_ult_u] > size[par_ult_v])
        {
            swap(par_ult_v, par_ult_u);
        }

        parent[par_ult_u] = par_ult_v;
        size[par_ult_v] += size[par_ult_u];
        size[par_ult_u] = 0;

        return;
    }
};
void makeGraph(ll n)
{
    par.resize(n + 1, 0);
    dis.resize(n + 1, 1e9);
    vis.resize(n + 1, 0);
    adj.resize(n + 1);
    adj_w.resize(n + 1);
    indegree.resize(n + 1);

    return;
}
void addEdge(ll x, ll y)
{
    // go from x----->y
    adj[x].push_back(y);

    indegree[y]++;

    return;
}
void addEdgeWeight(ll x, ll y, ll c)
{
    // go from x----->y with weight c
    adj_w[x].push_back({y, c});
    return;
}

/*---------------------------------TEMPLATE  ENDS --------------------------------------------------------------------------------------*/
void solve()
{
    ll n, m;
    cin >> n >> m;
    vector<vector<ll>> v(m);
    vll freq(n + 1, 0);
    rep(i, 0, m)
    {
        ll x;
        cin >> x;
        rep(j, 0, x)
        {
            ll y;
            cin >> y;
            v[i].push_back(y);
            freq[v[i][j]]++;
        }
    }
    ll flag = 0;
    rep(i, 0, m)
    {
        rep(j, 0, v[i].size())
        {

            if (freq[v[i][j]] > (m + 1) / 2)
            {
                flag = 1;
            }
        }
    }
    // rep(i, 0, n)
    // {
    //     cout << freq[i] << " ";
    // }
    // cout << endl;
    // cout << flag << endl;
    if (!flag)
    {
       cout<<"YES"<<endl;
        rep(i, 0, m)
        {
            cout << v[i][0] << " ";
        }
        cout << endl;
    }
    else
    {
        ll mx = 0;
        ll mxfreq = 0;
        rep(i, 1, n+1)
        {
            if (freq[i] > mxfreq)
            {

                mxfreq = freq[i];
                mx = i;
                
            }
        }
        priority_queue<pll, vpll, greater<pll>> pq;
        rep(i, 0, m)
        {

            rep(j, 0, v[i].size())
            {
                if (v[i][j] == mx)
                {
                    pq.push({v[i].size(), i});
                    break;
                }
            }
        }
        ll ctr = (m + 1) / 2;
        vll ans(m, 0);
        while (ctr != 0)
        {
            pll x = pq.top();
            pq.pop();
            ans[x.s] = mx;
            ctr--;
        }
        rep(i, 0, m)
        {
            if (!ans[i])
            {   ll f12=0;
                rep(j, 0, v[i].size())
                {
                    if (v[i][j] != mx)
                    {
                        ans[i] = v[i][j];
                        f12=1;
                        break;
                    }
                }
                if(!f12){
                    cout<<"NO"<<endl;
                    return;
                }
            }
        }
        cout<<"YES"<<endl;
        rep(i,0,m){
            cout<<ans[i]<<" ";
        }
        cout<<endl;
    }

    return;
}
/*-----------------------------------------------------------------------------------------------------------------------*/
signed main()
{
    fastio;
    ll t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}