← 返回题目列表

Codeforces · 1914/G1

G1. 灯泡(简易版)

中文机器翻译题面 查看原题

这个问题的简单版本和困难版本仅在 $$$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$$$ 为模)。

示例

输入 #1

4
2
2 2 1 1
2
1 2 2 1
2
1 2 1 2
5
3 4 4 5 3 1 1 5 2 2

输出 #1

2 4
1 2
1 4
2 8