310438: CF1833E. Round Dance

E. Round Dancetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

$n$ people came to the festival and decided to dance a few round dances. There are at least $2$ people in the round dance and each person has exactly two neighbors. If there are $2$ people in the round dance then they have the same neighbor on each side.

You decided to find out exactly how many dances there were. But each participant of the holiday remembered exactly one neighbor. Your task is to determine what the minimum and maximum number of round dances could be.

For example, if there were $6$ people at the holiday, and the numbers of the neighbors they remembered are equal $[2, 1, 4, 3, 6, 5]$, then the minimum number of round dances is$1$:

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

and the maximum is $3$:

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

Input

The first line contains a positive number $t$ ($1 \le t \le 10^4$) — the number of test cases. The following is a description of the test cases.

The first line of the description of each test case contains a positive number $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of people at the holiday.

The second line of the description of each test case contains $n$ integers $a_i$ ($1 \le a_i \le n, a_i \neq i$) — the number of the neighbor that the $i$th person remembered.

It is guaranteed that the test cases are correct and corresponds to at least one division of people into round dances.

It is guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output two integers — the minimum and maximum number of round dances that could be.

ExampleInput

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

Output

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

题目大意：
E. 圆舞

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

输出数据格式：
对于每个测试用例，输出两个整数——可能的最小和最大圆舞数量。题目大意： E. 圆舞 有 $ 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 $。 输出数据格式： 对于每个测试用例，输出两个整数——可能的最小和最大圆舞数量。