Most Popular Friend

Problem code: LOKBIL

All submissions for this problem are available.

Anna Hazare is a well known social activist in India.

On 5th April, 2011 he started "Lokpal Bill movement".

Chef is very excited about this movement. He is thinking of contributing to it. He gathers his cook-herd and starts thinking about how our community can contribute to this.

All of them are excited about this too, but no one could come up with any idea. Cooks were slightly disappointed with this and went to consult their friends.

One of the geekiest friend gave them the idea of spreading knowledge through Facebook. But we do not want to spam people's wall. So our cook came up with the idea of dividing Facebook users into small friend groups and then identify the most popular friend in each group and post on his / her wall. They started dividing users into groups of friends and identifying the most popular amongst them.

The notoriety of a friend is defined as the averaged distance from all the other friends in his / her group. This measure considers the friend himself, and the trivial distance of '0' that he / she has with himself / herself.

The most popular friend in a group is the friend whose notoriety is least among all the friends in the group.

Distance between X and Y is defined as follows:
Minimum number of profiles that X needs to visit for reaching Y's profile(Including Y's profile). X can open only those profiles which are in the friend list of the current opened profile. For Example:
- Suppose A is friend of B.
- B has two friends C and D.
- E is a friend of D.

Now, the distance between A and B is 1, A and C is 2, C and E is 3.

So, one of our smart cooks took the responsibility of identifying the most popular friend in each group and others will go to persuade them for posting. This cheeky fellow knows that he can release his burden by giving this task as a long contest problem.

Now, he is asking you to write a program to identify the most popular friend among all the friends in each group. Also, our smart cook wants to know the average distance of everyone from the most popular friend.

Input

Friends in a group are labelled with numbers to hide their Facebook identity. The first line of input contains the number of groups in which users are divided. First line of each group contains the number of friends that belong to that group. ith line of each group contains the space separated friend list of 'i'. You are assured that each friend's profile can be accessed by the profile of every other friend by following some sequence of profile visits.

Output

Your output contains the most popular friend name label along with the average distance (space separated) from all other friends (including himself / herself) in six digits of precision. There might be multiple most popular friend, in that case output the friend labelled with least number.

Note:

Each person in a group have atleast one friend and he/she cannot be in his/her own friend list.
Number of friends in a group cannot be more than 100.
There are atmost 100 groups.

Example

Input:
1
6
3
5
1 4
3 5 6
2 4 6
4 5

Output:
4 1.166667
Author: ashwin_jain
Date Added: 14-06-2011
Time Limit: 1 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

I was getting a wrong answer

neildalvi69 @ 11 Jul 2011 04:49 PM
I was getting a wrong answer (again and again...) bcoz i had used a float for casting and not double :p

i am still getting WA :(

zoobiedoobie @ 11 Jul 2011 09:22 PM
i am still getting WA :( ...is there any way to find out the test case for which its failing?

@neildalvi69 :thanks ...did

evanescent @ 12 Jul 2011 12:09 AM
@neildalvi69 :thanks ...did the same mistake and was equally frustated if not more...ouch!!

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

HELP

Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:

 

  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • If you are still having problems, see a sample solution here.

CodeChef is a global programming communityCodeChef hosts online programming competitions