Orden de ordeño (Oro)#10388
Las vacas del granjero John, numeradas de a como siempre, resulta que tienen demasiado tiempo libre en sus pezuñas. Como consecuencia, han desarrollado una compleja jerarquía social relacionada con el orden en el que el granjero John las ordeña cada mañana.
Tras semanas de estudio, el granjero John ha hecho observaciones sobre la estructura social de sus vacas. Cada observación es una lista ordenada de algunas de sus vacas, lo que significa que esas vacas deben ser ordeñadas en el mismo orden en el que aparecen en la lista. Por ejemplo, si una de las observaciones del granjero John es la lista , el granjero John debe ordeñar la vaca en algún momento antes que la vaca , y la vaca en algún momento antes que la vaca .
Las observaciones del granjero John están priorizadas, así que su objetivo es maximizar el valor tal que su orden de ordeño cumpla las condiciones dadas por las primeras observaciones. Si varios órdenes de ordeño cumplen esas primeras condiciones, el granjero John sigue una antigua tradición según la cual las vacas con números menores tienen más rango que las vacas con números mayores, por lo que preferiría ordeñar primero a las vacas con los números más pequeños. Más formalmente, si varios órdenes de ordeño cumplen estas condiciones, el granjero John quiere usar el lexicográficamente menor. Un orden es lexicográficamente menor que un orden si existe tal que x_i = y_i para todo i < j y x_j < y_j (en otras palabras, los dos órdenes coinciden hasta cierta posición, en la cual tiene un elemento menor que ).
Ayuda al granjero John a determinar el mejor orden en el que ordeñar a sus vacas.
La primera línea contiene dos enteros y m~(1 \le n \le 10^5, 1 \le m \le 5 \cdot 10^4). Cada una de las siguientes líneas describe una observación: la línea (i + 1)-ésima describe la observación y comienza con el número m_i de vacas en la observación, seguido de m_i enteros — los números de esas vacas en el orden requerido. La suma de todos los m_i no supera 2 \cdot 10^5.
Imprime enteros — una permutación de los números de a que indique el orden en el que el granjero John debe ordeñar a sus vacas.
Aquí, el granjero John tiene vacas. Debe ordeñar la vaca antes que la vaca , y la vaca antes que la vaca (la primera observación); la vaca antes que la vaca (la segunda observación); y la vaca antes que la vaca , y la vaca antes que la vaca (la tercera observación). Las dos primeras observaciones pueden cumplirse simultáneamente, pero el granjero John no puede cumplir las tres a la vez, ya que eso exigiría que la vaca fuera antes que la vaca y la vaca antes que la vaca .
Por lo tanto, hay dos órdenes que cumplen las dos primeras observaciones: 1, 4, 2, 3 y 4, 1, 2, 3; el primero es lexicográficamente menor.
Ejemplo 1