Codeforces Round 874 (Div. 3) |
---|
Закончено |
$$$n$$$ людей пришли на праздник и решили станцевать несколько хороводов. В хороводе не менее $$$2$$$-х людей и у каждого человека есть ровно два соседа, если в хороводе $$$2$$$ человека, с обоих сторон один и тот же сосед.
Вы решили узнать, сколько именно было хороводов. Но каждый участник праздника запомнил ровно одного соседа. Ваша задача — определить, какое минимальное и максимальное число хороводов могло быть.
Например, если на празднике было $$$6$$$ человек, и номера соседей, которых они запомнили, равны $$$[2, 1, 4, 3, 6, 5]$$$ соответственно, то хороводов могло быть минимум $$$1$$$:
Первая строка содержит положительное число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка описания каждого набора входных данных содержит положительное число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество людей на празднике.
Вторая строка описания каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le n, a_i \neq i$$$) — номер соседа, которого запомнил $$$i$$$-й человек.
Гарантируется, что входные данные корректны и соответствуют хотя бы одному разбиению людей на хороводы.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите два целых числа — минимальное и максимальное количество хороводов, которое могло быть.
1062 1 4 3 6 562 3 1 5 6 492 3 2 5 6 5 8 9 822 144 3 2 152 3 4 5 165 3 4 1 1 253 5 4 1 266 3 2 5 4 365 1 4 3 4 2
1 3 2 2 1 3 1 1 1 2 1 1 1 1 2 2 1 2 1 1
Название |
---|