Dear friends from across China, welcome to Shenyang! As the problem setters, along with the entire staff, we are deeply honored to have all of you here to enjoy a well-prepared event and witness the ninth consecutive year that Northeastern University (NEU) has hosted the ICPC Shenyang Regional Contest.
The past years have been challenging for most individuals. Human society underwent the COVID-19 pandemic, yet we fought against it and triumphed. Humanity continues to be tested when it seems like the Night Howlers have eroded some people's minds. And for the lovely university where we are currently situated, it has just successfully concluded its centennial celebration, turning over a new page for the next century. So, those are what inspired us to name this intro problem. We sincerely hope one can strive constantly for dreams rather than being willing to become the tears of the times. We also hope one can heal the world with new-age technologies, not to steer our civilization to a sunset!
As an integral part of Northeastern University's centennial celebration, the drone display utilized various colors to illuminate the night sky, creating pieces of stunning aerial artwork. In the intro problem, you are going to meet with a seemingly NP-hard task related to it.
Drone Display by Northeastern University Suppose that there are $$$n$$$ scenes in the drone display. The palette of each scene can be described by a set of integers identifying different colors, and we say the main color of a scene is the color with the largest integer in its palette.
The drone operator intends to arrange the orders of the scenes. For each pair of adjacent scenes after the reordering, if the main color of the previous scene is one of the colors present in the palette of the following scene, a transition will be contributed. Can you help construct an arrangement of scenes such that the number of transitions is maximized?
More formally, let $$$S_i$$$ be the set of integers which describes the palette of the $$$i$$$-th scene. You need to construct a permutation $$$p_1,p_2,\ldots,p_n$$$ such that $$$\sum_{i=1}^{n-1}{\left[\max\{S_{p_{i}}\} \in S_{p_{i+1}}\right]}$$$ is maximized among all the permutations of length $$$n$$$, where $$$\left[\max\{S_{p_{i}}\} \in S_{p_{i+1}}\right]$$$ is $$$1$$$ when $$$\max\{S_{p_{i}}\} \in S_{p_{i+1}}$$$ and $$$0$$$ when $$$\max\{S_{p_{i}}\} \notin S_{p_{i+1}}$$$.
Recall that a permutation of length $$$n$$$ is a sequence of $$$n$$$ integers in which every integer from $$$1$$$ to $$$n$$$ appears exactly once.
The first line contains an integer $$$n$$$ ($$$2 \le n \le 10^5$$$), denoting the number of scenes in the drone display.
In the $$$i$$$-th of the next $$$n$$$ lines, an integer $$$m_i$$$ ($$$m_i \ge 1$$$) comes first, denoting the number of colors in the palette of the $$$i$$$-th scene. Then $$$m_i$$$ distinct integers $$$a_{i,1}, a_{i,2}, \ldots, a_{i,m_i}$$$ ($$$0 \le a_{i,j} \le 10^9$$$) follow, each identifying a color in the palette.
It is guaranteed that the sum of $$$m_i$$$ over $$$i=1,2,\ldots,n$$$ does not exceed $$$2 \times 10^5$$$.
In the first line, output an integer indicating the maximum attainable number of transitions among all arrangements of scenes.
In the second line, output a permutation $$$p_1,p_2,\ldots,p_n$$$ denoting that the $$$p_i$$$-th scene is played during the $$$i$$$-th period of time in chronological order. Your construction should maximize the number of transitions. If there are multiple arrangements of scenes that maximize the number of transitions, you may choose any to output its corresponding permutation.
53 1 2 42 2 32 1 31 22 4 5
3 4 2 3 1 5
3 1 1 1 2 1 3
0 1 2 3
In the first sample case, scene $$$4$$$ to scene $$$2$$$, scene $$$2$$$ to scene $$$3$$$, scene $$$1$$$ to scene $$$5$$$ can all contribute a transition.
In the second sample case, no scenes share the common color. Thus, any permutation of length $$$3$$$ will be acceptable.
