CF1482C Basic Diplomacy

Aleksey 有 $n$ 个朋友。他现在正在度假，所以他有 $m$ 天可以玩这款新流行的合作游戏！但由于这是合作游戏，Aleksey 每天都需要一位队友。 在每一天中，只有部分朋友有空可以一起玩，其他人则没有空。每天 Aleksey 必须从当天有空的朋友中选择一位来邀请一起玩（他们当然都会同意）。然而，如果某位朋友被选中的次数严格超过 $ \left\lceil\dfrac{m}{2}\right\rceil $ 次，其他所有朋友都会感到不满。Aleksey 当然不想让任何人不高兴。 请帮助他选择每天的队友，使得没有任何一位朋友被选中的次数严格超过 $ \left\lceil\dfrac{m}{2}\right\rceil $ 次。

每个测试点包含多个测试用例。第一行包含测试用例个数 $t$（$1 \le t \le 10\,000$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1\leq n, m\leq 100\,000$），分别表示朋友的数量和可以玩的天数。 接下来的 $m$ 行中，第 $i$ 行包含一个整数 $k_i$（$1\leq k_i\leq n$），后跟 $k_i$ 个不同的整数 $f_{i1}, \ldots, f_{ik_i}$（$1\leq f_{ij}\leq n$），表示第 $i$ 天有空的朋友编号。 保证所有测试用例中 $n$ 和 $m$ 的总和不超过 $100\,000$。保证所有测试用例中所有天的 $k_i$ 之和不超过 $200\,000$。

对于每个测试用例，若无法满足条件，输出一行 “NO”。 否则，第一行输出 “YES”，第二行输出 $m$ 个用空格分隔的整数 $c_1, \ldots, c_m$，其中 $c_i$ 表示第 $i$ 天选择的朋友编号（必须是当天有空的朋友之一）。 同一个编号出现的次数不得超过 $ \left\lceil\dfrac{m}{2}\right\rceil $ 次。如果有多种方案，输出任意一种均可。

由 ChatGPT 4.1 翻译