Handshakes And Bump Fists

0

0 votes
Medium
Problem

An army has n soldiers. The soldiers are numbers from 1 to n. The army has a superiority hierarchy. Every soldier has one immediate superior. The superior of a superior of a soldier is also a superior to that soldier. So, a soldier may have one or more superiors but only one immediate superior.

Every soldier has to congratulate every other soldier. For a pair of soldiers if one of them is the superior of the other, they will shake hands. Otherwise, they will bump their fists.

You are given the list of immediate superior of all soldiers, your job is to tell how many handshakes and fist bumps will be there. Print the count of handshakes and fist bumps.

NOTE: Among all soldiers, there is one soldier who does not have any superior. He is the commander of the whole army.

Input Format :

Line 1 : Integer t, the number of test cases.

Line 2 : The first line of each test case contains n, the number of soldiers.

Line 3 : The next line contains n space separated integers. The ith integer represents the immediate superior of the ith soldier.The immediate superior of the commander of the army will be '0'.

Output Format :

Print two space separated integers, the number of handshakes and the number of fist bumps.

Contraints :

1<=t<=10

1<=n<=100000

Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?