E. Хороводы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

$$$n$$$ людей пришли на праздник и решили станцевать несколько хороводов. В хороводе не менее $$$2$$$-х людей и у каждого человека есть ровно два соседа, если в хороводе $$$2$$$ человека, с обоих сторон один и тот же сосед.

Вы решили узнать, сколько именно было хороводов. Но каждый участник праздника запомнил ровно одного соседа. Ваша задача — определить, какое минимальное и максимальное число хороводов могло быть.

Например, если на празднике было $$$6$$$ человек, и номера соседей, которых они запомнили, равны $$$[2, 1, 4, 3, 6, 5]$$$ соответственно, то хороводов могло быть минимум $$$1$$$:

  • $$$1 - 2 - 3 - 4 - 5 - 6 - 1$$$
и максимум $$$3$$$:
  • $$$1 - 2 - 1$$$
  • $$$3 - 4 - 3$$$
  • $$$5 - 6 - 5$$$
Входные данные

Первая строка содержит положительное число $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите два целых числа — минимальное и максимальное количество хороводов, которое могло быть.

Пример
Входные данные
10
6
2 1 4 3 6 5
6
2 3 1 5 6 4
9
2 3 2 5 6 5 8 9 8
2
2 1
4
4 3 2 1
5
2 3 4 5 1
6
5 3 4 1 1 2
5
3 5 4 1 2
6
6 3 2 5 4 3
6
5 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