← 返回题目列表

Codeforces · 1482/C

C. 基本外交

中文机器翻译题面 查看原题

Aleksey 有 $$$n$$$ 朋友。他现在也在度假,所以他有 $$$m$$$ 天来玩这个新的病毒式合作游戏!但由于它是合作性的,Aleksey 在 $$$m$$$ 的每一天都需要一名队友。

在这些日子里,每天都会有一些朋友可以玩,而其他人则不能。每天,阿列克西必须选择一位可用的朋友来邀请他玩游戏(当然,他们总是同意)。然而,如果他们中的任何一个碰巧被严格选择超过 $$$\left\lceil\dfrac{m}{2}\right\rceil$$$ 次,那么所有其他朋友都会被冒犯。当然,阿列克谢不想冒犯任何人。

帮助他选择队友,以便没有人被严格选择超过 $$$\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}$$$, ..., $$$f_{ik_i}$$$ ($$$1\leq f_{ij}\leq n$$$),以空格分隔 — 当天 $$$i$$$ 上可用好友的索引。

保证所有测试用例的 $$$n$$$ 和 $$$m$$$ 之和不超过 $$$100\,000$$$。保证所有测试用例全天的所有 $$$k_i$$$ 总和不超过 $$$200\,000$$$。

输出

打印每个测试用例的答案。如果没有办法实现目标,则打印“NO”。

否则,在第一行打印“YES”,并在第二行打印 $$$m$$$ 空格分隔的整数 $$$c_1$$$, ..., $$$c_m$$$。每个 $$$c_i$$$ 必须表示 $$$i$$$ 当天所选的朋友(因此必须是 $$$f_{ij}$$$ 之一)。

值出现的次数不得超过 $$$\left\lceil\dfrac{m}{2}\right\rceil$$$ 次。如果有多个可能的答案,请打印其中任何一个。

示例

输入 #1

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

输出 #1

YES
1 2 1 1 2 3 
NO