Two Friends
Contest: Educational Codeforces Round 165 (Rated for Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, implementation, math

Monocarp wants to throw a party. He has $$$n$$$ friends, and he wants to have at least $$$2$$$ of them at his party.

The $$$i$$$-th friend's best friend is $$$p_i$$$. All $$$p_i$$$ are distinct, and for every $$$i \in [1, n]$$$, $$$p_i \ne i$$$.

Monocarp can send invitations to friends. The $$$i$$$-th friend comes to the party if both the $$$i$$$-th friend and the $$$p_i$$$-th friend receive an invitation (note that the $$$p_i$$$-th friend doesn't have to actually come to the party). Each invitation is sent to exactly one of the friends.

For example, if $$$p = [3, 1, 2, 5, 4]$$$, and Monocarp sends invitations to the friends $$$[1, 2, 4, 5]$$$, then the friends $$$[2, 4, 5]$$$ will come to the party. The friend $$$1$$$ won't come since his best friend didn't receive an invitation; the friend $$$3$$$ won't come since he didn't receive an invitation.

Calculate the minimum number of invitations Monocarp has to send so that at least $$$2$$$ friends come to the party.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases.

Each test case consists of two lines:

- the first line contains one integer $$$n$$$ ($$$2 \le n \le 50$$$) — the number of friends;
- the second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$; $$$p_i \ne i$$$; all $$$p_i$$$ are distinct).

Output format:
Print one integer — the minimum number of invitations Monocarp has to send.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first testcase, Monocarp can send invitations to friends $$$4$$$ and $$$5$$$. Both of them will come to the party since they are each other's best friends, and both of them have invitations.

In the second testcase, Monocarp can send invitations to friends $$$1, 2$$$ and $$$3$$$, for example. Then friends $$$1$$$ and $$$2$$$ will attend: friend $$$1$$$ and his best friend $$$2$$$ have invitations, friend $$$2$$$ and his best friend $$$3$$$ have invitations. Friend $$$3$$$ won't attend since his friend $$$4$$$ doesn't have an invitation. It's impossible to send invitations to fewer than $$$3$$$ friends in such a way that at least $$$2$$$ come.

In the third testcase, Monocarp can send invitations to both friends $$$1$$$ and $$$2$$$, and both of them will attend.

Example input:
3
5
3 1 2 5 4
4
2 3 4 1
2
2 1

Example output:
2
3
2

Editorial:
Obviously, you can't send fewer than $$$2$$$ invitations. Since all $$$p_i \neq i$$$, you need to send at least $$$2$$$ invitations ($$$i$$$ and $$$p_i$$$) in order for at least some friend $$$i$$$ to come.
On the other hand, you never need to send more than $$$3$$$ invitations. You can always send invitations to friends $$$i, p_i$$$, and $$$p_{p_i}$$$, so that $$$i$$$ and $$$p_i$$$ come.
Now we need to determine the condition for when two invitations are enough. That is, we send invitations to friends $$$i$$$ and $$$j$$$, and both of them come. This means $$$p_i = j$$$ and $$$p_j = i$$$. This check is already enough to solve the problem in $$$O(n^2)$$$. But you can think further and see that since $$$j = p_i$$$, the second check becomes $$$p_{p_i} = i$$$. This means it is enough to iterate over friend $$$i$$$ and check if $$$p_{p_i} = i$$$ for at least one of them.
Overall complexity: $$$O(n)$$$ per testcase.