CF1914G1 Light Bulbs (Easy Version)

本题的简单版和困难版仅在 $n$ 的约束条件上有所不同。在简单版中，所有测试用例中 $n^2$ 的总和不超过 $10^6$。此外，每个测试用例中的 $n$ 不超过 $1000$。 有 $2n$ 个灯泡排成一排。每个灯泡的颜色为 $1$ 到 $n$ 之间的某个数（每种颜色恰好有两个灯泡）。 最开始，所有灯泡都是关闭的。你需要选择一个灯泡集合 $S$，将其中的灯泡最初点亮。之后，你可以任意次、任意顺序地执行以下操作： - 选择两个同色的灯泡 $i$ 和 $j$，其中恰好有一个是点亮的，将另一个也点亮； - 选择三个灯泡 $i, j, k$，其中 $i$ 和 $k$ 都已点亮且颜色相同，$j$ 位于它们之间（$i < j < k$），将 $j$ 点亮。 你希望选择一个集合 $S$，使得通过上述操作，最终可以点亮所有灯泡。 请计算两个数： - 你最初需要点亮的灯泡集合 $S$ 的最小大小； - 满足条件的最小集合 $S$ 的数量（对 $998244353$ 取模）。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 1000$），表示灯泡对的数量。 每个测试用例的第二行包含 $2n$ 个整数 $c_1, c_2, \dots, c_{2n}$（$1 \le c_i \le n$），其中 $c_i$ 表示第 $i$ 个灯泡的颜色。对于每种颜色 $1$ 到 $n$，恰好有两个灯泡为该颜色。 输入的额外约束：所有测试用例中 $n^2$ 的总和不超过 $10^6$。

对于每个测试用例，输出两个整数： - 最小的初始点亮集合 $S$ 的大小； - 满足条件的最小集合 $S$ 的数量（对 $998244353$ 取模）。

由 ChatGPT 4.1 翻译