← 返回题目列表

Codeforces · 1833/E

E. 圆舞

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

$$$n$$$ 人们来到节日并决定跳几段圆舞。圆舞会中至少有 $$$2$$$ 人,并且每个人恰好有两个邻居。如果圆舞中有 $$$2$$$ 人,那么他们每一边都有同一个邻居。

您决定找出到底有多少支舞蹈。但假期的每个参与者都准确地记得一个邻居。您的任务是确定圆舞的最小和最大数量。

例如,如果节日有 $$$6$$$ 人,并且他们记住的邻居数量等于 $$$[2, 1, 4, 3, 6, 5]$$$,则圆舞的最少数量为 $$$1$$$:

- $$$1 - 2 - 3 - 4 - 5 - 6 - 1$$$

- $$$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$$$。

输出

对于每个测试用例,输出两个整数——可能的最小和最大圆舞数量。

示例

输入 #1

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

1 3
2 2
1 3
1 1
1 2
1 1
1 1
2 2
1 2
1 1