P16540 [EGOI 2026] Pizza Masters / Ovenmasters

You are a journalist from the “Italian Excellent Pizza Masters Competition”. The best $N$ pizza chefs in Italy have just competed here to decide who is the greatest pizza master. Each chef baked one pizza, and then the judges ranked the pizzas. Each pizza received a unique rank from $0$ (best) to $N - 1$ (worst). Each chef also received the same rank as their pizza. After the competition, it is time for the pizza feast. All chefs will attend, and each person brings their own pizza to the feast. The chefs arrive one by one in some order (not necessarily by rank). There are $M \leq N$ tables at the feast, numbered from $0$ to $M - 1$. The first $M$ chefs who arrive place their pizzas on tables $0$ to $M - 1$ in arrival order. The remaining $N - M$ chefs want to eat a pizza that is better than the one they made, but not too much better, so they will not feel inferior. Each time a chef arrives, they choose, among the pizzas currently on the tables, the pizza that is better than their own but has the worst rank among those better ones. They sit next to the table of the chosen pizza, eat the entire chosen pizza, and finally leave their own pizza on that table for later chefs (possibly) to eat. If there is no suitable pizza for an arriving chef (because all pizzas on the tables are worse than their own), the chef leaves sadly and takes their own pizza away (that is, they do not leave their pizza). The example below shows a feast with $M = 2$ tables, where chefs arrive in the following rank order: $1, 0, 3, 5, 4, 2$. This feast corresponds to the first sample input and output. :::align{center}  The first $M = 2$ chefs place their pizzas on the empty tables ($0$, $1$) in arrival order. ::: :::align{center}  Once all tables are occupied, each arriving chef goes to the table that has (under this rule) the pizza that is better than their own but has the worst rank among those better ones (shown by arrows), eats that pizza, and leaves their own. If there is no better pizza, the chef leaves sadly (no arrow). ::: In your article, you want to report the order in which the chefs arrived at the pizza feast. Unfortunately, because you were obsessed with all the tasty pizzas, you forgot to write down their arrival order. Luckily, on each table you can find a stack of trays, which records, in serving order, the pizzas that were served at this table. :::align{center}  The tray stacks for the first sample. Each stack lists, in arrival order (from bottom to top, where the bottom is earlier), the chefs who ate at this table. The highlighted trays are the pizzas that remained on the tables when the feast ended. ::: You want to use this information to reconstruct the chefs’ arrival order. You realize there may be multiple possible orders, so to get full score you must report the lexicographically smallest valid order. A sequence $a_0, a_1, \dots, a_{N-1}$ is lexicographically smaller than a sequence $b_0, b_1, \dots, b_{N-1}$ if there exists an index $0 \leq t < n$ such that for all $i < t$, $a_i = b_i$, and $a_t < b_t$.

The first line contains two integers $N$ and $M$, representing the number of chefs and the number of tables. Then there are $M$ lines, each describing the stack of trays on one table. Line $i$ starts with an integer $T_i$, the number of trays on table $i$, followed by $T_i$ integers $b_{i, j}$, the rank of the $j$-th pizza served at this table.

If there is no possible order that satisfies the conditions, output `NO`. If there exists a possible order, output `YES`. In this case, output a second line containing $N$ integers $a_0, a_1, \cdots, a_{N-1}$, the chefs’ ranks in arrival order. If there are multiple such permutations, you should output the lexicographically smallest one. Note that partially correct answers may still receive points; see the scoring section for details.

### Sample Explanation The first sample input and output correspond to the pictures in the statement. In particular, in Figures 1 and 2, the arrival order of the chefs is the lexicographically smallest valid arrival order: $1, 0, 3, 5, 4, 2$. In the second sample, the tray stacks are impossible, because there is no arrival order that makes the chef ranked 5 leave sadly. Therefore, the answer is `NO`. In the third and fifth samples, the tray stacks are also impossible (no arrival order can produce them), so the answer is `NO`. In the fourth sample ($N=3$, $M=1$), there is only one possible arrival order: $0, 2, 1$. In the sixth sample ($N=12$, $M=4$), note that the numbers $0$ and $1$ do not appear among the values $b_{i,j}$. This means that at some time during the feast, both chefs $0$ and $1$ left sadly. The sample output shows the lexicographically smallest valid arrival order. Of course, there are other valid arrival orders; for example, $2, 5, 6, 7, 8, 1, 3, 4, 9, 10, 11, 0$. Outputting `YES` followed by any other valid order (instead of the lexicographically smallest one) will be considered partially correct, with a score of 40%. ### Constraints - $1 \leq M \leq N \leq 300\ 000$。 - $0 \leq b_{i,j} \leq N-1$。 - All $b_{i, j}$ are distinct. - $1 \leq T_i \leq N$。 ### Scoring Your program will be tested on testdata divided into several subtasks. To get the score for a subtask, you must solve all testdata in that subtask correctly. A solution that only answers the first line (`YES` or `NO`) correctly gets 20% of the points. A solution that answers the first line correctly and outputs **any valid** order (when the answer is `YES`) gets an additional 20%. To get the remaining 60%, you must output the lexicographically smallest valid order when the first line is `YES`. - **Subtask 0** [$0$ points]: Samples. - **Subtask 1** [$20$ points]: $M = 1$. - **Subtask 2** [$10$ points]: $M = 2, N \le 200$, and the sum of all $T_i$ is $N$ (in other words, no chef leaves sadly). - **Subtask 3** [$20$ points]: $M \le N \le 200$, and the sum of all $T_i$ is $N$ (in other words, no chef leaves sadly). - **Subtask 4** [$20$ points]: $M \le 10$. - **Subtask 5** [$30$ points]: No additional constraints. Translated by ChatGPT 5