/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2008 by Doina Logofatu

in C#: Michael Gärtner
************************************************/

using System;
using System.Text;
using System.IO;

namespace P_Kap02_01
{
    class P01_BoxInBox
    {
        private class Box : IComparable
        {
            private int[] dimensions;
            private int index;

            public Box(int boxIndex, int[] boxDimensions)
            {
                this.index = boxIndex;
                this.dimensions = boxDimensions;
            }

            public int CompareTo(object obj)
            {
                Box otherBox = (Box)obj;
                int rt = 0;
                for ( int i = 0; i < this.dimensions.Length && rt == 0; i++ )
                {
                    rt = this.dimensions[i] - otherBox.dimensions[i];
                }
                return rt;
            }

            public int getIndex
            {
                get { return index; }
            }

            public Boolean fitIn(Box otherBox)
            {
                Boolean fit = true;
                for ( int i = 0; fit && i < this.dimensions.Length; i++ )
                {
                    fit = this.dimensions[i] < otherBox.dimensions[i];
                }
                return fit;
            }
        }

        static void Main(string[] args)
        {
            FileStream fsIn = new FileStream("schachteln.in", FileMode.Open);
            StreamReader sr = new StreamReader(fsIn);

            FileStream fsOut = new FileStream("schachteln.out", FileMode.OpenOrCreate);
            StreamWriter aus = new StreamWriter(fsOut);

            string[] sArray; // Hilfsvariable fürs Einlesen

            // Daten einlesen
            sArray = sr.ReadLine().Split(' ');
            Box[] boxes = new Box[int.Parse(sArray[0])];
            int numDimensions = int.Parse(sArray[1]);
            for ( int i = 0; i < boxes.Length; i++ )
            {
                sArray = sr.ReadLine().Split(' ');
                int[] boxDimensions = new int[numDimensions];
                for ( int j = 0; j < numDimensions; j++ )
                {
                    boxDimensions[j] = int.Parse(sArray[j]);
                }
                Array.Sort(boxDimensions);
                boxes[i] = new Box(i, boxDimensions);
            }
            sr.Close();
            fsIn.Close();
            Array.Sort(boxes);

            // Algorithmus
            int[] v = new int[boxes.Length];          
            int[] vPred = new int[boxes.Length];            
            for ( int i = 0; i < boxes.Length; i++ )
            {
                v[i] = 1;
                vPred[i] = -1;
            }
            int indexMax = 0;

            for ( int i = 0; i < boxes.Length; i++ )
            {
                Box currBox = boxes[i];
                for ( int j = 0; j < i; j++ )
                {
                    if ( boxes[j].fitIn(currBox) && v[j] + 1 > v[i] )
                    {
                        v[i] = v[j] + 1;
                        vPred[i] = j;
                    }
                }
                if ( v[i] > v[indexMax] )
                {
                    indexMax = i;
                }
            }

            // Ausgabe
            aus.Write("Laenge: ");
            aus.WriteLine(v[indexMax]);
            aus.WriteLine("---------------");
            StringBuilder bf = new StringBuilder();
            for ( int currIdx = indexMax; currIdx >= 0; currIdx = vPred[currIdx] )
            {
                bf.Insert(0, ' ').Insert(0, (boxes[currIdx].getIndex + 1));
            }
            aus.WriteLine(bf);
            aus.WriteLine("******************************");

            aus.Close();
            fsOut.Close();
        }
    }
}