Stacking Boxes

在数学或计算机科学里，有些概念在一维或二维时还蛮简单的，但到N维就会显得非常复杂。试想一个n维的「盒子」：在二维空间里，盒子（2，3）可代表一个长为2个单位，宽为3个单位的盒子；在三维空间里，盒子（4，8，9）则是一个4*8*9（长、宽、高）的盒子。至于在六维空间里，也许我们不清楚（4，5，6，7，8，9）长得怎样，不过我们还是可以分析这些盒子的特性。 在此问题里，我们要算出一组n维盒子里，它们的「最长套入列表」：b1，b2，……，bk，其中每个盒子bi都可以「放入」盒子bi+1中（1 <= i < k） 考虑两个盒子D =（d1，d2，……，dn），E =（e1，e2，……，en）。如果盒子D的n个维，能够存在一种重排，使得重排后，D每一维的量度都比E中相对应的维的量度还要小，则我们说盒子D能「放入」盒子E。（用比较不严谨的讲法，这就好像我们将盒子D翻来翻去，看看能不能摆到E里面去。不过因为我们考虑的是任一重排，所以实际上盒子不只可转来转去，甚至还可以扭曲。）（还是看看下面的例子说明好了）。 譬如说，盒子D =（2，6）能够被放入盒子E =（7，3）里，因为D可以重排变为（6，2），这样子D的每个维的量度都比E里对应的维还要小。而盒子D =（9，5，7，3）就没办法放进盒子E =（2，10，6，8），因为就算再怎摸重排D里的维，还是没办法符合「放入」的条件。不过F =（9，5，7，1）就可以放入E了，因为F可以重排成（1，9，5，7），这样就符合了放入的条件。 我们今定义「放入」如下：对于任两个盒子D =（d1，d2，……，dn）和E =（e1，e2，……，en），如果存在一种1..n的重排π，使得对于任何的1 <= i <= n，皆有dπ（i）< ei，则我们说盒子D能「放入」盒子E。 Input 输入包含多组测试数据。每组测试数据的第一列有两个数字：第一个是盒子的数量k，然后是盒子的维数n。 接下来有k列，每列有n个整数表示一个盒子的n个维的量度，量度之间由一个以上的空白做区隔。第一列表示第一个盒子，第二列表示第二个盒子，依此类推。 此问题里，盒子的维数最小是1，最大是10，并且每组测试数据中盒子的个数最多为30个。 Output 对于每一组测试数据，你必须输出两列数字：第一列是「最长套入列表」的长度，第二列是按照内外顺序，印出「最长套入列表」里盒子的编号（其中编号是按照在输入档案的每组数列里所出现的顺序，例如第一个盒子就是1号.. .等等。）最里面的盒子（或是最小的）摆在第一个，再来是次小的，依此类推。 如果对于每一组的盒子，存在两个以上的「最长套入列表」，输出任何一个均可。 翻译贡献者UID：60576

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=39 [PDF](https://uva.onlinejudge.org/external/1/p103.pdf) 



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

5
3 1 2 4 5
4
7 2 5 6