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

Difficulty: interview

Starter code:

Solutions:
from collections import deque
from sys import stdin
import psyco
psyco.full()

graph = [[]]
WHITE, GRAY, BLACK = 0, 1, 2

def notoriety(x, f_count):
    queue = deque([x])
    d = [0 for i in range(f_count+1)]
    p = [0 for i in range(f_count+1)]
    color = [WHITE for i in range(f_count+1)]
    while len(queue) > 0:
        top = queue.pop()
        for node in graph[top]:
            if color[node] == WHITE:
                queue.appendleft(node)
                color[node], p[node], d[node] = GRAY, top, d[top] + 1
        color[top] = BLACK
    return sum(d)/(f_count*1.0)
        
def main():
    groups = int(stdin.readline())
    for g in range(groups):
        global graph
        graph = [[]]
        no_of_friends = int(stdin.readline())
        for i in range(no_of_friends):
            graph.append(list(map(int,stdin.readline().split())))
        min_notoriety, popular = 10000000, -1 # yet another magic number
        for f in range(1,no_of_friends+1):
            curr_not = notoriety(f, no_of_friends)
            if  curr_not < min_notoriety:
                min_notoriety,popular = curr_not, f
        assert popular != -1
        print(popular, "%.6f" %min_notoriety)

def __starting_point():
    main()

__starting_point()

from collections import deque
from sys import stdin
import psyco
psyco.full()

graph = [[]]
WHITE, GRAY, BLACK = 0, 1, 2

def notoriety(x, f_count):
    queue = deque([x])
    d = [0 for i in range(f_count+1)]
    p = [0 for i in range(f_count+1)]
    color = [WHITE for i in range(f_count+1)]
    while len(queue) > 0:
        top = queue.pop()
        for node in graph[top]:
            if color[node] == WHITE:
                queue.appendleft(node)
                color[node], p[node], d[node] = GRAY, top, d[top] + 1
        color[top] = BLACK
    return sum(d)/(f_count*1.0)
        
def main():
    groups = int(stdin.readline())
    for g in range(groups):
        global graph
        graph = [[]]
        no_of_friends = int(stdin.readline())
        for i in range(no_of_friends):
            graph.append(list(map(int,stdin.readline().split())))
        min_notoriety, popular = 10000000, -1 # yet another magic number
        for f in range(1,no_of_friends+1):
            curr_not = notoriety(f, no_of_friends)
            if  curr_not < min_notoriety:
                min_notoriety,popular = curr_not, f
        assert popular != -1
        print(popular, "%.6f" %min_notoriety)

def __starting_point():
    main()

__starting_point()

from collections import deque
import psyco
psyco.full()

graph = [[]]
WHITE, GRAY, BLACK = 0, 1, 2

def notoriety(x, f_count):
    queue = deque([x])
    d = [0 for i in range(f_count+1)]
    p = [0 for i in range(f_count+1)]
    color = [WHITE for i in range(f_count+1)]
    while len(queue) > 0:
        top = queue.pop()
        for node in graph[top]:
            if color[node] == WHITE:
                queue.appendleft(node)
                color[node], p[node], d[node] = GRAY, top, d[top] + 1
        color[top] = BLACK
    return sum(d)/(f_count*1.0)
        
def main():
    groups = int(input())
    for g in range(groups):
        global graph
        graph = [[]]
        no_of_friends = int(input())
        for i in range(no_of_friends):
            graph.append(list(map(int,input().split())))
        min_notoriety, popular = 10000000, -1 # yet another magic number
        for f in range(1,no_of_friends+1):
            curr_not = notoriety(f, no_of_friends)
            if  curr_not < min_notoriety:
                min_notoriety,popular = curr_not, f
        assert popular != -1
        print(popular, "%.6f" %min_notoriety)

def __starting_point():
    main()

__starting_point()