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. i^{th} 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.

----- Sample Input 1 ------ 
1
6
3
5
1 4
3 5 6
2 4 6
4 5
----- Sample Output 1 ------ 
4 1.166667

Source: codechef | Difficulty: MEDIUM
Tags: Graph algorithms

Graph traversal

Implementation

Mathematics

Data structures


Solutions:
import heapq

def dijkstra(graph, start):
	distances = {vertex: float('inf') for vertex in range(len(graph))}
	distances[start] = 0
	heap = [(0, start)]
	while heap:
		(current_distance, current_vertex) = heapq.heappop(heap)
		if current_distance > distances[current_vertex]:
			continue
		for neighbor in graph[current_vertex]:
			distance = current_distance + 1
			if distance < distances[neighbor]:
				distances[neighbor] = distance
				heapq.heappush(heap, (distance, neighbor))
	return distances
for _ in range(int(input())):
	g = int(input())
	graph = []
	for i in range(g):
		graph.append([int(x) - 1 for x in input().split()])
	(m, i) = (10 ** 10, 0)
	for start in range(g):
		distances = dijkstra(graph, start)
		minimal_distance = sum(distances.values())
		if minimal_distance < m:
			m = minimal_distance
			i = start + 1
	print(i, '{:.6f}'.format(m / g))


from collections import deque

def getavg(s, al):
	tot = 0
	q = deque([[s, 0]])
	vis = set([s])
	while q:
		(h, d) = q.popleft()
		tot += d
		for fri in al[h]:
			if fri not in vis:
				q.append([fri, d + 1])
				vis.add(fri)
	return tot
for tc in range(int(input())):
	num = int(input())
	adjlist = [0]
	pop = -1
	avgdist = 10000000
	for i in range(num):
		fri = list(map(int, input().split()))
		adjlist.append(fri)
	for i in range(1, num + 1):
		avg = getavg(i, adjlist)
		avg = avg / num
		if avg < avgdist:
			avgdist = avg
			pop = i
	print(pop, end=' ')
	print('%.6f' % avgdist)


g = int(input())
for _ in range(g):
	n = int(input())
	connections = {}
	visitas = {}
	distancia_a_amigos = {}
	for i in range(1, n + 1):
		connections[i] = list(map(int, input().split()))
		visitas[i] = False
		distancia_a_amigos[i] = 0
	amigo_mas_popular = 1
	promedio_mas_bajo = False
	for i in range(1, n + 1):
		visitas_i = visitas.copy()
		visitas_i[i] = True
		distancia_a_amigos_i = distancia_a_amigos.copy()
		cola = [i]
		suma = 0
		suma_total = 0
		while len(cola) > 0:
			actual = cola.pop(0)
			for j in connections[actual]:
				if not visitas_i[j]:
					visitas_i[j] = True
					distancia_a_amigos_i[j] = distancia_a_amigos_i[actual] + 1
					suma_total += distancia_a_amigos_i[j]
					cola.append(j)
		import decimal
		promedio = decimal.Decimal(suma_total) / decimal.Decimal(n)
		if promedio_mas_bajo == False or promedio < promedio_mas_bajo:
			promedio_mas_bajo = promedio
			amigo_mas_popular = i
	print(amigo_mas_popular, round(promedio_mas_bajo, 6))


from sys import stdin
from collections import defaultdict, deque
T = int(input())
for t in range(T):
	g = {}
	N = int(input())
	for i in range(N):
		g[i + 1] = list(map(int, input().split()))
	popular = 1
	popularcount = 1000000
	for i in range(1, N + 1):
		dist = [None for i in range(N)]
		q = deque()
		q.append(i)
		dist[i - 1] = 0
		while len(q) > 0:
			current = q.popleft()
			for neigh in g[current]:
				if dist[neigh - 1] is None:
					dist[neigh - 1] = dist[current - 1] + 1
					q.append(neigh)
		notiority = sum(dist) / N
		if notiority < popularcount:
			popularcount = notiority
			popular = i
	print(popular, end=' ')
	print('%.6f' % popularcount)


from sys import stdin
from collections import defaultdict, deque
g = int(input())

def getDistancesToFriends(graph, start):
	distances = [None] * (len(graph) + 1)
	distances[start] = 0
	queue = [start]
	while queue:
		current = queue.pop(0)
		for neigh in graph[current]:
			if distances[neigh] is None:
				distances[neigh] = distances[current] + 1
				queue.append(neigh)
	return distances
for t in range(g):
	n = int(input())
	g = {}
	for i in range(n):
		g[i + 1] = list(map(int, input().split()))
	frnd = 1
	minDist = float('inf')
	for i in range(1, n + 1):
		dist = getDistancesToFriends(g, i)[1:]
		avg = sum(dist) / len(dist)
		if avg < minDist:
			minDist = avg
			frnd = i
	print(frnd, '{0:.6f}'.format(minDist))


def getDist(graph, start):
	distances = [None] * (len(graph) + 1)
	distances[start] = 0
	queue = [start]
	while queue:
		current = queue.pop(0)
		for neigh in graph[current]:
			if distances[neigh] is None:
				distances[neigh] = distances[current] + 1
				queue.append(neigh)
	return distances
for t in range(int(input())):
	n = int(input())
	gr = {}
	for i in range(n):
		gr[i + 1] = list(map(int, input().split()))
	frnd = 1
	minDist = float('inf')
	for i in range(1, n + 1):
		dist = getDist(gr, i)[1:]
		avg = sum(dist) / len(dist)
		if avg < minDist:
			minDist = avg
			frnd = i
	print(frnd, '{0:.6f}'.format(minDist))


tn = int(input())
for _ in range(tn):
	n = int(input())
	ar = dict()
	for i in range(1, n + 1):
		ar[i] = list(map(int, input().split()))
	(mvsm, midx) = (-1, -1)
	for i in range(1, n + 1):
		visli = {i}
		tdis = 0
		queue = [(i, 0)]
		while queue:
			(nd, dis) = queue.pop(0)
			tdis += dis
			for x in ar[nd]:
				if x not in visli:
					visli.add(x)
					queue.append((x, dis + 1))
		if mvsm == -1:
			mvsm = tdis
			midx = i
		elif mvsm > tdis:
			mvsm = tdis
			midx = i
	print(midx, '{:.6f}'.format(mvsm / n))


g = int(input())

def getDistancesToFriends(graph, start):
	distances = [None] * (len(graph) + 1)
	distances[start] = 0
	queue = [start]
	while queue:
		current = queue.pop(0)
		for neighbor in graph[current]:
			if distances[neighbor] is None:
				distances[neighbor] = distances[current] + 1
				queue.append(neighbor)
	return distances
for t in range(g):
	n = int(input())
	g = {}
	for i in range(n):
		g[i + 1] = list(map(int, input().split()))
	imin = 1
	min = 2000
	for i in range(1, n + 1):
		a = getDistancesToFriends(g, i)[1:]
		avg = sum(a) / len(a)
		if avg < min:
			min = avg
			imin = i
	print(imin, '{0:.6f}'.format(min))


import math

def getShortestDistance(adjList, popularNode):
	queue = [popularNode]
	visited = [False for i in range(len(adjList))]
	distance = [-1 for i in range(len(adjList))]
	curr = 0
	while len(queue) > 0:
		size = len(queue)
		for i in range(size):
			frontNode = queue.pop(0)
			distance[frontNode] = curr
			visited[frontNode] = True
			for node in adjList[frontNode]:
				if not visited[node]:
					visited[node] = True
					queue.append(node)
		curr += 1
	return distance
groups = int(input())
while groups > 0:
	groups -= 1
	nodes = int(input())
	adjList = [[] for i in range(nodes + 1)]
	popularNode = -1
	minAvg = math.inf
	for i in range(1, nodes + 1):
		adjList[i] = list(map(int, input().split()))
	for i in range(1, nodes + 1):
		distance = getShortestDistance(adjList, i)
		avg = sum(distance[1:]) / nodes
		if avg < minAvg:
			minAvg = avg
			popularNode = i
	print(popularNode, '{:.6f}'.format(minAvg))


import sys
if len(sys.argv) >= 2:
	sys.stdin = open(sys.argv[1])

def dijkstra(adj, src):
	n = len(adj)
	dist = [float('inf')] * n
	dist[src] = 0
	q = [src]
	while q:
		u = q.pop(0)
		for v in adj[u]:
			if dist[v] > dist[u] + 1:
				dist[v] = dist[u] + 1
				q.append(v)
	return dist

def avg(adj, src):
	dist = dijkstra(adj, src)
	_sum = 0
	for i in range(1, len(dist)):
		_sum += dist[i]
	return _sum / (len(dist) - 1)

def solve():
	n = int(input())
	adj = [set() for _ in range(n + 1)]
	for i in range(1, n + 1):
		a = input().split()
		adj[i] = set(map(int, a))
	_min = 1000000000.0
	friend = 1
	for i in range(1, n + 1):
		val = avg(adj, i)
		if val < _min:
			_min = val
			friend = i if friend else friend
	print(friend, f'{_min:.6f}')
t = 1
t = int(input())
for _ in range(t):
	solve()


G = int(input())
tf = [0] * G
m = []
for g in range(0, G):
	tf[g] = int(input())
	m.append({})
	for i in range(0, tf[g]):
		m[g].update({i + 1: [int(p) for p in input().split()]})
for grp in range(0, G):
	dict1 = m[grp]
	u = []
	mmember = 1
	for member in range(0, tf[grp]):
		visited = [0] * tf[grp]
		visited[member] = 1
		dist = 0
		q = []
		time = 1
		q.append([member, time])
		while 0 in visited:
			(o, y) = q.pop(0)
			for v in dict1[o + 1]:
				if visited[v - 1] == 0:
					visited[v - 1] = 1
					q.append([v - 1, y + 1])
					dist = dist + y
		u.append(dist)
	ans = u.index(min(u)) + 1
	print(ans, '{:.6f}'.format(round(min(u) / tf[grp], 6)))


from collections import deque

def bfs(i, adj, vis, n):
	q = deque()
	q.append(i)
	vis[i] = 1
	dist = 0
	notoreity = 0
	while len(q) != 0:
		for i in range(len(q)):
			t = q.popleft()
			notoreity += dist
			for val in adj[t]:
				if not vis[val]:
					vis[val] = 1
					q.append(val)
		dist += 1
	return notoreity / n

def solve(adj, n):
	vis = [0 for _ in range(n)]
	nototreity = bfs(0, adj, vis, n)
	fr = 1
	for i in range(1, n):
		vis = [0 for _ in range(n)]
		_notoreity = bfs(i, adj, vis, n)
		if _notoreity < nototreity:
			nototreity = _notoreity
			fr = i + 1
	print(fr, '%.6f' % nototreity)
T = int(input())
for _ in range(T):
	n = int(input())
	adj = [[] for _ in range(n)]
	for i in range(n):
		l = list(map(int, input().split()))
		for val in l:
			adj[i].append(val - 1)
	solve(adj, n)


from collections import deque

def find_avg_dist(adj, u):
	adj_size = len(adj)
	visited = [0] * adj_size
	distance = [0] * adj_size
	Q = deque([u])
	visited[u] = 1
	while len(Q):
		x = Q.popleft()
		for e in adj[x]:
			if not visited[e]:
				distance[e] = distance[x] + 1
				visited[e] = 1
				Q.append(e)
	return sum(distance)
for _ in range(int(input())):
	N = int(input())
	adj = {}
	for i in range(N):
		adj[i] = list(map(lambda x: int(x) - 1, input().split()))
	avg_vals = [find_avg_dist(adj, i) for i in range(N)]
	a = min(avg_vals)
	print('{} {:.6f}'.format(avg_vals.index(a) + 1, a / N))


from collections import deque

def solve(adj, i):
	seen = {i: 0}
	queue = deque([i])
	total = 0
	while len(queue) > 0:
		node = queue.popleft()
		dist = seen[node]
		for n in adj[node]:
			if n not in seen:
				seen[n] = dist + 1
				total += dist + 1
				queue.append(n)
	return total
groups = int(input())
for _ in range(groups):
	n = int(input())
	adj = dict()
	for i in range(1, n + 1):
		adj[i] = list(map(int, input().split()))
	distances = [solve(adj, i) for i in range(1, n + 1)]
	min_dist = min(distances)
	min_index = distances.index(min_dist) + 1
	print(min_index, f'{min_dist / n:.6f}')


def bfs(source, adj):
	visted = set()
	visted.add(source)
	queue = []
	queue.append((source, 0))
	s = 0
	while queue:
		(src, dist) = queue.pop(0)
		for k in adj[src]:
			if k not in visted:
				visted.add(k)
				queue.append((k, dist + 1))
				s += dist + 1
	return s
group = int(input())
for i in range(group):
	N = int(input())
	friends = {}
	for j in range(1, N + 1):
		friends[j] = list(map(int, input().split(' ')))
	distance = []
	for j in range(1, N + 1):
		distance.append(bfs(j, friends))
	ans = distance.index(min(distance)) + 1
	mindistavg = min(distance) / N
	avg = round(mindistavg, 6)
	print(ans, '{:.6f}'.format(mindistavg))


def bfs(start, friend_dict):
	visited = set()
	queue = [(start, 0)]
	visited.add(start)
	s = 0
	while queue:
		(friend, dist) = queue.pop(0)
		s += dist
		for x in friend_dict[friend]:
			if x not in visited:
				queue.append((x, dist + 1))
				visited.add(x)
	return s
for _ in range(int(input())):
	n = int(input())
	friend_dict = {}
	for i in range(1, n + 1):
		li = list(map(int, input().split()))
		friend_dict[i] = li
	mini = float('inf')
	at_source = None
	for i in range(1, n + 1):
		if bfs(i, friend_dict) < mini:
			mini = bfs(i, friend_dict)
			at_source = i
	res = mini / n
	res = round(res, 6)
	print(at_source, f'{res:.6f}')


def vamsi(adj, n, i):
	q = []
	used = [0] * (n + 1)
	d = [0] * (n + 1)
	p = [0] * (n + 1)
	s = i
	q.append(s)
	used[s] = 1
	p[s] = -1
	while len(q) != 0:
		v = q[0]
		del q[0]
		for u in adj[v]:
			if used[u] == 0:
				used[u] = 1
				q.append(u)
				d[u] = d[v] + 1
				p[u] = v
	return d
import math
for _ in range(int(input())):
	n = int(input())
	adj = {}
	for i in range(1, n + 1):
		l = list(map(int, input().split()))
		adj[i] = l
	s = math.inf
	s1 = 0
	for i in range(1, n + 1):
		k = vamsi(adj, n, i)
		if k.count(0) == 2 and sum(k) / n < s:
			s = min(s, sum(k) / n)
			s1 = i
	print('{} {:.6f}'.format(s1, s))


def bfs(source, adj):
	visited = set()
	visited.add(source)
	queue = []
	queue.append((source, 0))
	s = 0
	while queue:
		(curr, dist) = queue.pop(0)
		for node in adj[curr]:
			if node not in visited:
				visited.add(node)
				queue.append((node, dist + 1))
				s += dist + 1
	return s
for _ in range(int(input())):
	n = int(input())
	friends = {}
	for i in range(1, n + 1):
		friends[i] = tuple(map(int, input().split()))
	distance = []
	for i in range(1, n + 1):
		distance.append(bfs(i, friends))
	most_popular = distance.index(min(distance)) + 1
	f = min(distance) / n
	average = round(f, 6)
	print(most_popular, '{:.6f}'.format(f))


class Connections:

	def __init__(self, n):
		self.num = n
		self.friends = {}
		self.lst = []
		self.social()
		self.length()

	def social(self):
		for i in range(1, self.num + 1):
			self.friends[i] = tuple(map(int, input().split()))

	def search(self, vec):
		visited = set()
		visited.add(vec)
		queue = [(vec, 0)]
		s = 0
		while queue:
			q = queue[0]
			queue.pop(0)
			for i in self.friends[q[0]]:
				if i not in visited:
					queue.append((i, q[1] + 1))
					visited.add(i)
					s += q[1] + 1
		return s

	def length(self):
		for i in range(1, self.num + 1):
			self.lst.append(self.search(i))
T = int(input())
for _ in range(T):
	con = Connections(int(input()))
	x = min(con.lst)
	i = con.lst.index(x) + 1
	print(i, '{:.6f}'.format(round(x / con.num, 6)))


class Graph:

	def __init__(self, V):
		self.V = V
		self.adj = [[] for i in range(V + 1)]

	def addEdge(self, v, w):
		self.adj[v].append(w)
		self.adj[w].append(v)

	def BFS(self, i):
		level = ['useless']
		for j in range(1, self.V + 1):
			level.append(-1)
		Q = []
		level[i] = 0
		Q.append(i)
		while Q:
			j = Q[0]
			del Q[0]
			for k in self.adj[j]:
				if level[k] == -1:
					level[k] = 1 + level[j]
					Q.append(k)
		return level
t = int(input())
for i in range(t):
	N = int(input())
	g = Graph(N)
	for i in range(1, N + 1):
		arr = [int(p) for p in input().split()]
		g.adj[i] = arr
	countarr = ['useless']
	for i in range(1, N + 1):
		countarr.append(0)
	for i in range(1, N + 1):
		arrlist = g.BFS(i)
		countarr[i] = sum(arrlist[1:]) / N
	maxx = min(countarr[1:])
	ind = countarr.index(maxx)
	arr2 = g.BFS(ind)
	ans = sum(arr2[1:]) / N
	print(ind, '{:.6f}'.format(ans))


from typing import List
from collections import deque

class Node:
	value: int
	friends: 'List[Node]'

	def __init__(self, value: int):
		self.value = value
		self.friends = []

def bfs(nodes: List[Node], start_node: int, n: int):
	queue = deque([nodes[start_node]])
	distances = [-1 for _ in range(n)]
	distances[start_node] = 0
	while queue:
		node = queue.popleft()
		for friend in node.friends:
			if distances[friend.value] < 0:
				distances[friend.value] = distances[node.value] + 1
				queue.append(friend)
	return distances

def find_most_popular(nodes: List[Node], n: int) -> (int, float):
	min_distance: float = 1000000000.0
	min_distance_idx: int = -1
	for i in range(1, n):
		node = nodes[i]
		distances = bfs(nodes, i, n)
		distance = sum(distances[1:]) / (n - 1)
		if distance < min_distance:
			min_distance = distance
			min_distance_idx = i
	return (min_distance_idx, min_distance)

def main():
	groups = int(input())
	for _ in range(groups):
		n = int(input())
		if n > 1:
			n += 1
			nodes = [Node(i) for i in range(n)]
			for i in range(1, n):
				friends = [int(f) for f in input().split()]
				nodes[i].friends.extend([nodes[f] for f in friends])
			(popular_node, min_distance) = find_most_popular(nodes, n)
			print(f'{popular_node} {min_distance:.6f}')
		else:
			input()
			print('1 0')
main()