New year gifts
new year gifts
problem statement
every year in school during the new year time, the teacher conducts an event for the students called new year card to increase the friendship among students.
student roll numbers from 1 to n take part in the event total n number of students. each student i is assigned a different student si, to which student i has to make a new year greeting card. each student is assigned to exactly one other student, and nobody is assigned to themselves. in other words, all si must be distinct integers between 1 and n, and for any i, si≠i must hold.
every year these assignments were done by the teacher but this year due to the covid-19 situation as the teacher was busy with other school work. all the students have been asked to whom they wish to make a card.
every student (ith) wishes to make a card for jth student. while i!=j , means a student cannot wish to give himself a card,and every student has to wish for exactly 1 out of the n-1 remaining students.
find a valid assignment s that maximizes the number of fulfilled wishes of the students.
input format
the first line of the input gives the number of test cases t to be answered. first-line integer n size of the array
the next line contains n space-separated integers representing the wishes of the students in order 1 to n.
output format
in each separate line print the maximum number of students whose wishes will be fulfilled.
constraints:
1<= t<= 1000
1<= n<= 10^5
1<= array[i] <= n
sum of n over all the test cases does not exceed 10^5.
sample input:
1
7
6 4 6 2 4 5 6
sample output:
4
explanation:
in this permutation, 4 students will be happy which is the maximum there can be other permutations as well but not with more than 4 students will be happy in any order.
one of the permutations can be [6 ,4 ,7, 2 ,3 ,5 ,1] or [3,4,6,2,1,5,7]