De fondo

Algunos conceptos en matemáticas y en Ciencias de la Computación son simples en una o dos dimensiones pero son más complejos cuando se extienden a dimensiones arbitrarias.Consideremos cuando resolvemos ecuaciones diferenciales en varias dimensiones y analizando la topología de un n-dimensional hipercubico. Lo anterior es mucho más complicado que su dimensión relativa única mientras el posterior soporta un asombroso parecido a su "clase baja" prima.

El problema

Algunos conceptos en matemáticas y en Ciencias de la Computación son simples en una o dos dimensiones pero son más complejos cuando se extienden a dimensiones arbitrarias.Consideremos cuando resolvemos ecuaciones diferenciales en varias dimensiones y analizando la topología de un n-dimensional hipercubico. Lo anterior es mucho más complicado que su dimensión relativa única mientras el posterior soporta un asombroso parecido a su "clase baja" prima.tex2html_wrap_inline40 (largo, ancho y alto). En 6 dimensiones no es muy claro que es lo que la caja (4,5,6,7,8,9) representa, pero nosotros podemos analizar las propiedades de la caja como la suma de sus dimensiones.

IEn este problema debes analizar una propiedad de un grupo de cajas n-dimensionales. Tienes que determinar el largo de la cadena anidada de cajas, que es una secuencia de cajas tex2html_wrap_inline44 stal que cada caja tex2html_wrap_inline46 este anidado en la caja tex2html_wrap_inline48 ( tex2html_wrap_inline50 .

Una caja D = (tex2html_wrap_inline52 ) anidado en una caja E= ( tex2html_wrap_inline54 ) si existe alguna reconfiguración de los tex2html_wrap_inline56 tal que cuando reconfiguramos cada dimensión esta es menor que la dimensión correspondiente de la caja E. Esto corresponde a doblar la caja D para ver si cabe en la caja E. Sin embargo, puesto que alguna reconfiguración es suficiente la caja D puede deformarse.(ver los ejemplos abajo)

Por ejemplo, la caja D = (2,6) anidado en la caja E = (7,3) puesto que D puede ser reconfigurado como (6,2) a fin de que cada dimensión sea menor que dimensión correspondiente en E. La caja D = (9,5,7,3) no se anida en la caja E = (2,10,6,8) puesto que reconfigurando D no se puede colocar en E, pero F = (9,5,7,1) puede ser anidado en la caja E puesto que F puede ser reconfigurado como (1,9,5,7) el cual se anida en E.

Formalmente, nosotros definimos anidación como lo que sigue: La caja D = ( tex2html_wrap_inline52 ) se anida en la caja E = ( tex2html_wrap_inline54 ) si existe una permutación tex2html_wrap_inline62 de tex2html_wrap_inline64 tal que ( tex2html_wrap_inline66 ) cabe en ( tex2html_wrap_inline54 ) esto si tex2html_wrap_inline70 para todo tex2html_wrap_inline72 .

La entrada

La entrada consiste de una serie de secuencias de cajas. Cada secuencia de caja comienza con una línea que consiste de el número de cajas k en la secuencia seguido por la dimensionalidad de las cajas n (en la misma línea).

Esta línea es seguida por k lineas, una línea por caja con las n medidas de cada caja en una línea separados por uno o más espacios. La tex2html_wrap_inline82 línea en la secuencia ( tex2html_wrap_inline84 ) da las médidas para la tex2html_wrap_inline82 caja.

Puede haber varias secuencias de cajas en el archivo de entrada. Tu programa debe procesar todos ellos y determinar, para cada secuencia cuál de las k cajas resuelve la cadena anidada y el tamaño de la cadena anidada. (el número de cajas en la cadena).

En este problema la máxima dimensionalidad dimensionalidad es 10 y la mínima dimensionalidad es 1. El número máximo de cajas en una secuencia es 30.

La salida

Para cada secuencia de cajas en el archivo de entrada, imprima el tamaño del largo de la cadena anidada en una línea seguida en la siguiente línea por una lista de las cajas que comprenden esta cadena en orden. La más pequeña de las cajas de la cadena anidada debe ser listada primero, la siguiente caja (si existe otra caja) debe ser listado segundo, etc.

Las cajas deben ser numeradas según el orden en el cual ellos aparecen en el archivo de entrada (primera caja es caja1, etc.)

Si existe más de un largo de cadena anidada algúno de estos puede ser la salida.

Ejemplo de entrada

5 2
3 7
8 10
5 2
9 11
21 18
8 6
5 2 20 1 30 10
23 15 7 9 11 3
40 50 34 24 14 4
9 10 11 12 13 14
31 4 18 8 27 17
44 32 13 19 41 19
1 2 3 4 5 6
80 37 47 18 21 9

Ejemplo de salida

5
3 1 2 4 5
4
7 2 5 6