Problem Description

Translated from ROI 2021 D1T4.

There are $n$ employees in the company, numbered from $1$ to $n$. Employee $1$ is the founder of the company, and every other employee has exactly one direct supervisor. The organizational structure forms a tree: for each node, its parent is its supervisor, and its children are its subordinates. Employees who have subordinates are called managers, and the others are called consultants. The company structure guarantees that each manager has at most $8$ subordinates, including the founder.

The founder decides to report recent product improvements to the investors. Each improvement is the work result of some consultant in the company. All improvements are numbered in the order they happened.

Each consultant needs to choose one improvement and report it to their manager. Therefore, each consultant’s report contains exactly one improvement.

Each manager, including the founder, needs to collect their subordinates’ reports and concatenate them into one sequence, keeping each subordinate’s internal order unchanged and placing the sequences as contiguous blocks. For example, if the first manager’s report contains improvements $[1, 3]$ and the second manager’s report contains improvements $[2, 4, 10]$, then there are two possible results: $[2, 4, 10, 1, 3]$ or $[1, 3, 2, 4, 10]$. Other combinations are impossible.

The founder wants to present these improvements in the most reasonable way, so he wants the improvements in his report to be in increasing order by their numbers. Help each consultant choose which improvement to report, and help each manager choose the order in which to concatenate their subordinates’ reports, so that the improvements in the founder’s report can be arranged in chronological order.

Input Format

The first line contains an integer $n$ ($2 \le n \le 100000$), the number of employees in the company. The next $n$ lines describe each employee. Each line is one of the following:

• If the employee is a manager or the founder, the line starts with the number $1$, followed by the number $k_i$ ($1 \le k_i \le 8$), the number of subordinates of this manager, and then $k_i$ distinct numbers in the range from $2$ to $n$, which are the IDs of their subordinates.
• If the employee is a consultant, the line starts with the number $2$, followed by the number $m_i$, the number of improvements they can report, and then $m_i$ distinct integers in the range from $1$ to $100000$, which are the corresponding improvement numbers.

It is guaranteed that each improvement is mentioned by exactly one consultant, i.e. all improvements mentioned by consultants are distinct.

Output Format

If it is impossible to concatenate the reports, output No.

If it is possible to concatenate the reports, output Yes, and then output the following in order of employee IDs:

• If the employee is a manager, output the order of their subordinates in the concatenation.
• If the employee is a consultant, output the improvement number they should report.

Note: If you do not output a concatenation method but correctly determine whether it is possible, you will get $10\%$ partial score.

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

Hint

Sample Explanation:

In sample 2, no specific concatenation method is output, so only partial score can be obtained. A correct output should be:

Yes
2 3
1
2

In sample 3, each consultant can only choose that single improvement number. The third manager has two possible report sequences: $[1, 3]$ or $[3, 1]$. The first manager has four possible report sequences, considering all possibilities for the third manager: $[1, 3] + [2] = [1, 3, 2],[2] + [1, 3] = [2, 1, 3],[3, 1 ] + [2] = [3, 1, 2],[2] + [3, 1] = [2, 3, 1]$, but in none of these reports are the improvements sorted by time.

Constraints:

For $100\%$ of the testdata, $n,\sum m_i \le 100 000$ and $\max k_i\le8$。

Translated by ChatGPT 5