P11091 [ROI 2021] 工作报告 (Day 1)

题目描述

翻译自 [ROI 2021 D1T4](https://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-roi-2021-day1.pdf)。 公司中有 $n$ 个员工,编号从 $1$ 到 $n$。编号为 $1$ 的员工是公司的创始人,其他员工都有且只有一个直接上级。公司的组织结构形成了一棵树,每个节点的父节点是它的上级,而子节点是它的下属。拥有下属的员工被称为经理,其他员工被称为顾问。公司的结构保证每个经理最多有 $8$ 个下属,包括创始人。 创始人决定向投资者们汇报最近产品改进的情况。每个改进都是来自公司的某个顾问的工作成果。所有改进按照它们发生的时间顺序进行编号。 每个顾问需要选择一个改进并向他的经理汇报。因此,每个顾问的报告仅包含一个改进。 每个经理,包括创始人在内,需要汇总他们下属的报告,并按照报告的顺序将它们直接连续地组合起来。例如,如果第一个经理的报告包含改进 $[1, 3]$,而第二个经理的报告包含改进 $[2, 4, 10]$,那么可以得到两种组合结果:$[2, 4, 10, 1, 3]$ 或者 $[1, 3, 2, 4, 10]$,其他组合是不可能的。 创始人希望以尽可能合理的方式讲述这些改进,因此他希望在他的报告中改进按照编号的升序排列。请帮助每个顾问选择要汇报的改进,并帮助每个经理选择组合下属报告的顺序,以使得创始人的报告中的改进能够按照时间顺序排列。

输入格式

第一行包含一个整数 $n $($2 \le n \le 100000$),表示公司的员工数量。接下来的 $n$ 行描述每个员工,每行包含以下内容之一: - 如果员工是经理或创始人,则以数字 $1$ 开头,接下来是数字 $k_i $($1 \le k_i \le 8$),表示该经理的下属数量,然后是 $k_i$ 个不同的数字,范围在 $2$ 到 $n$,表示是其下属的员工编号。 - 如果员工是顾问,则以数字 $2$ 开头,接下来是数字 $m_i$,表示他可以汇报的改进数量,然后是 $m_i$ 个不同的整数,范围在 $1$ 到 $100000$,表示对应改进的编号。 保证每个改进都仅被一个顾问提及,即所有顾问提到的改进都是不同的。

输出格式

如果无法组合报告,输出 `No`。 如果能够组合报告,输出 `Yes`,然后你可以按照员工编号的顺序输出以下内容: - 如果员工是经理,则输出他的下属在组合报告中的顺序。 - 如果员工是顾问,则输出他需要汇报的改进编号。 注:如果不输出组合报告的方式但正确判断了是否能够组合报告,将会得到 $10\%$ 的部分分。

说明/提示

### 样例解释: 在样例二中,没有输出具体的组合方法,所以只能得到部分分。正确的输出应该是这样的: ```text Yes 2 3 1 2 ``` 在样例三中,每个顾问都只能选择那唯一的改进编号。第三位经理有两种可能的报告方式:$[1, 3]$ 或 $[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]$,但是在这些报告中没有一个改进是按照时间顺序排序的。 ### 数据范围: ![](https://cdn.luogu.com.cn/upload/image_hosting/mchn5bpr.png) 对于 $100\%$ 的数据,$n,\sum m_i \le 100 000$ 且 $\max k_i\le8$。