Codeforces Round 916 (Div. 3) |
---|
Закончено |
Простая и сложная версии этой задачи отличаются друг от друга только ограничениями на $$$n$$$. В сложной версии сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$. Кроме того, никаких дополнительных ограничений на значение $$$n$$$ в одиночном наборе входных данных нет.
В ряд расположены $$$2n$$$ лампочек. У каждой лампочки есть цвет от $$$1$$$ до $$$n$$$ (ровно по две лампочки каждого цвета).
Изначально все лампочки выключены. Вы выбираете некоторое множество лампочек $$$S$$$, которое вы изначально включите. После этого вы можете выполнять следующие операции в любом порядке любое количество раз:
Вы хотите выбрать такое множество лампочек $$$S$$$, которые вы изначально включаете, чтобы путем выполнения описанных операций можно было добиться того, чтобы все лампочки оказались включены.
Посчитайте два числа:
В первой строке входных данных содержится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют описания наборов.
В первой строке каждого набора задано одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество пар лампочек.
Во второй строке каждого набора заданы $$$2n$$$ целых чисел $$$c_1, c_2, \dots, c_{2n}$$$ ($$$1 \le c_i \le n$$$), где $$$c_i$$$ — цвет $$$i$$$-й лампочки. Для каждого цвета от $$$1$$$ до $$$n$$$ ровно две лампочки имеют этот цвет.
Дополнительное ограничение на входные данные: сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите два целых числа:
422 2 1 121 2 2 121 2 1 253 4 4 5 3 1 1 5 2 2
2 4 1 2 1 4 2 8
Название |
---|