Простая и сложная версии этой задачи отличаются друг от друга только ограничениями на \(n\). В простой версии сумма значений \(n^2\) по всем наборам входных данных не превосходит \(10^6\). Кроме того, \(n\) не превосходит \(1000\) в каждом наборе входных данных.
В ряд расположены \(2n\) лампочек. У каждой лампочки есть цвет от \(1\) до \(n\) (ровно по две лампочки каждого цвета).
Изначально все лампочки выключены. Вы выбираете некоторое множество лампочек \(S\), которое вы изначально включите. После этого вы можете выполнять следующие операции в любом порядке любое количество раз:
Вы хотите выбрать такое множество лампочек \(S\), которые вы изначально включаете, чтобы путем выполнения описанных операций можно было добиться того, чтобы все лампочки оказались включены.
Посчитайте два числа:
В первой строке входных данных содержится одно целое число \(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\).
Для каждого набора входных данных выведите два целых числа:
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
2 4 1 2 1 4 2 8
3000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач