嵌套箱问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

一个d 维箱(x1,x2,……,xd ) 嵌入另一个d 维箱(y1,y2,……,yd) 是指存在1,2,…,d 的一个排列π,使得 xπ1 < y1 ,  xπ2 < y2 ,…,  xπd < yd
(1)证明上述箱嵌套关系具有传递性;
(2)试设计一个有效算法,用于确定一个d维箱是否可嵌入另一个d维箱;
(3)给定由n 个d 维箱组成的集合{B1 ,B2 ,…… ,Bn } ,试设计一个有效算法找出这n 个d维箱中的一个最长嵌套箱序列,并用n和d 描述算法的计算时间复杂性。
给定由n个d维箱,试设计一个有效算法,找出这n个d维箱中的一个最长嵌套箱序列。

Input

输入数据含多个测试数据项。每个测试数据项的第一行中有2 个整数n 和d(n,d≤50),分别表示箱的个数和维数。其后n行每行有d个正整数,表示箱的各维的长度。

Output

对每个测试数据项,输出数据占有两行,第一行是其最长嵌套箱序列的长度,第二行是从小到大排列的最长嵌套箱序列。

Sample Input

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

Sample Output

5
3 1 2 4 5
4
7 2 5 6

Hint

Source