P13442 [GCJ 2009 #2] Stock Charts

你正在撰写报社的年度经济总结，目前你决定用几张图表来展示不同股票在过去一年的表现。你已经决定要展示 $n$ 支不同股票在一年中 $k$ 个时刻的价格。 一支股票的简单走势图，就是在平面上连接 $(0, \text{price}_0)$、$(1, \text{price}_1)$、……、$(k-1, \text{price}_{k-1})$ 这些点，其中 $\text{price}_i$ 表示该股票在第 $i$ 个时刻的价格。 为了节省版面，你发明了“叠加图表”的概念。一个叠加图表是由一条或多条简单走势图组成的，展示多支股票的价格（每支股票画一条线）。为了避免混淆，叠加图表中的不同股票曲线不能相交或相触。 给定 $n$ 支股票在 $k$ 个时刻的价格，请你计算，至少需要多少张叠加图表，才能展示所有股票的价格。

输入的第一行为一个整数 $T$，表示测试用例数。接下来是 $T$ 组测试数据，每组格式如下： $n\ k$ $\text{price}_{0,0}\ \text{price}_{0,1}\ \ldots\ \text{price}_{0,k-1}$ $\text{price}_{1,0}\ \text{price}_{1,1}\ \ldots\ \text{price}_{1,k-1}$ …… $\text{price}_{n-1,0}\ \text{price}_{n-1,1}\ \ldots\ \text{price}_{n-1,k-1}$ 其中 $\text{price}_{i,j}$ 为第 $i$ 支股票在第 $j$ 个时刻的价格。

对于每组测试数据，输出一行： Case #$X$: $Y$ 其中 $X$ 是测试用例编号（从 1 开始），$Y$ 是展示所有股票价格所需的最少叠加图表数。

**限制条件** - $1 \leq T \leq 100$ - $2 \leq k \leq 25$ - $0 \leq \text{price}_{i,j} \leq 1000000$ **小数据集** - 时间限制：2 秒 - $1 \leq n \leq 16$ **大数据集** - 时间限制：3 秒 - $1 \leq n \leq 100$ 翻译由 ChatGPT-4.1 完成。