#P11091. [ROI 2021 Day 1] 工作报告

    ID: 10377 Type: RemoteJudge 3000ms 1024MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>2021Special JudgeROI(俄罗斯)

[ROI 2021 Day 1] 工作报告

题目背景

翻译自 ROI 2021 D1T4

公司中有 nn 个员工,编号从 11nn。编号为 11 的员工是公司的创始人,其他员工都有且只有一个直接上级。公司的组织结构形成了一棵树,每个节点的父节点是它的上级,而子节点是它的下属。拥有下属的员工被称为经理,其他员工被称为顾问。公司的结构保证每个经理最多有 88 个下属,包括创始人。

创始人决定向投资者们汇报最近产品改进的情况。每个改进都是来自公司的某个顾问的工作成果。所有改进按照它们发生的时间顺序进行编号。

每个顾问需要选择一个改进并向他的经理汇报。因此,每个顾问的报告仅包含一个改进。

每个经理,包括创始人在内,需要汇总他们下属的报告,并按照报告的顺序将它们直接连续地组合起来。例如,如果第一个经理的报告包含改进 [1,3][1, 3],而第二个经理的报告包含改进 [2,4,10][2, 4, 10],那么可以得到两种组合结果:[2,4,10,1,3][2, 4, 10, 1, 3] 或者 [1,3,2,4,10][1, 3, 2, 4, 10],其他组合是不可能的。

题目描述

创始人希望以尽可能合理的方式讲述这些改进,因此他希望在他的报告中改进按照编号的升序排列。请帮助每个顾问选择要汇报的改进,并帮助每个经理选择组合下属报告的顺序,以使得创始人的报告中的改进能够按照时间顺序排列。

输入格式

第一行包含一个整数 nn 2n1000002 \le n \le 100000),表示公司的员工数量。接下来的 nn 行描述每个员工,每行包含以下内容之一:

  • 如果员工是经理或创始人,则以数字 11 开头,接下来是数字 kik_i 1ki81 \le k_i \le 8),表示该经理的下属数量,然后是 kik_i 个不同的数字,范围在 22nn,表示是其下属的员工编号。
  • 如果员工是顾问,则以数字 22 开头,接下来是数字 mim_i,表示他可以汇报的改进数量,然后是 mim_i 个不同的整数,范围在 11100000100000,表示对应改进的编号。

保证每个改进都仅被一个顾问提及,即所有顾问提到的改进都是不同的。

输出格式

如果无法组合报告,输出 No

如果能够组合报告,输出 Yes,然后你可以按照员工编号的顺序输出以下内容:

  • 如果员工是经理,则输出他的下属在组合报告中的顺序。
  • 如果员工是顾问,则输出他需要汇报的改进编号。

注:如果不输出组合报告的方式但正确判断了是否能够组合报告,将会得到 10%10\% 的部分分。

6
1 3 5 4 6
2 3 10 61 60
2 2 80 20
2 2 40 70
1 2 3 2
2 4 30 90 91 92
Yes
5 6 4
10
20
40
2 3
30
3
1 2 2 3
2 1 1
2 1 2
Yes
5
1 2 2 3
2 1 2
1 2 4 5
2 1 1
2 1 3
No

提示

样例解释:

在样例二中,没有输出具体的组合方法,所以只能得到部分分。正确的输出应该是这样的:

Yes
2 3
1
2

在样例三中,每个顾问都只能选择那唯一的改进编号。第三位经理有两种可能的报告方式:[1,3][1, 3][3,1][3, 1]。第一位经理有四种可能的报告方式,考虑到第三位经理的所有报告可能性:$[1, 3] + [2] = [1, 3, 2],[2] + [1, 3] = [2, 1, 3],[3, 1 ] + [2] = [3, 1, 2],[2] + [3, 1] = [2, 3, 1]$,但是在这些报告中没有一个改进是按照时间顺序排序的。

数据范围:

对于 100%100\% 的数据,n,mi100000n,\sum m_i \le 100 000maxki8\max k_i\le8