Description

在一个方格坐标系上，你有 $2n$ 个弹珠。这些弹珠被涂成 $n$ 种不同的颜色，每种颜色恰好有 $2$ 个弹珠。所有弹珠被依次放在坐标 $(1,0)$、$(2,0)$、$\ldots$、$(2n, 0)$ 上。

你的任务是为每种颜色画一条路径，将该颜色的两个弹珠连接起来。每条路径应由若干条垂直或水平的线段组成，且这些线段必须连接在网格点上。任意两条路径不能相交或相触。任意一条路径都不能穿过 $y=0$ 这条直线。每条路径只能在它所连接的两个弹珠的位置与 $y=0$ 相接，因此每条路径的首尾线段必须是竖直的。

给定弹珠的排列方式，返回一个解方案的最小高度，如果不存在合法解，则返回 $-1$。高度定义为所有路径所经过的最大 $Y$ 坐标与最小 $Y$ 坐标之差。

例如：

red red blue yellow blue yellow

一种可行的解法如下：

 +---+    +-----------+
 |   |    |           |
red red blue yellow blue yellow
                 |           |
                 +-----------+

在这个例子中，最小高度为 $2$。

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组的第一行为 $n$，表示弹珠颜色种类数。下一行为 $2n$ 个用空格分隔的单词，按从左到右顺序分别表示每个弹珠的颜色。每个颜色由小写字母（'a' 到 'z'）组成，长度不超过 $10$ 个字符。每种颜色恰好出现两次。

Output Format

对于每组测试数据，输出一行，格式如下：

Case #$x$:

其中 $x$ 是测试编号（从 $1$ 开始），后接一个最优解的最小高度。如果不存在合法解，输出 $-1$。

4
3
red red blue yellow blue yellow
3
red blue yellow red blue yellow
3
red blue yellow blue yellow red
3
red red blue blue yellow yellow

Case #1: 2
Case #2: -1
Case #3: 3
Case #4: 1

Hint

限制条件

• $1 \leq T \leq 50.$

小数据集（7 分）

• 时间限制：3 秒
• $1 \leq n \leq 20.$

大数据集（32 分）

• 时间限制：6 秒
• $1 \leq n \leq 500.$

翻译由 ChatGPT-4.1 完成。