Барни живет в USC (United States of Charzeh). USC состоит из n городов с номерами от 1 до n и n - 1 дорог между ними. Города и дороги в USC формируют корневое дерево (и Барни понятия не имеет, почему оно корневое). Корню дерева соответствует город номер 1. Таким образом, начиная в городе 1, по дорогам можно добраться до любого другого города.

Незнакомка завладела сердцем Барни, и теперь он хочет ее найти. Он начинает поиски в городе номер 1, и, (так как он Барни Стинсон, а не кто-то еще), и для поисков использует случайный поиск в глубину. Этот алгоритм можно описать с помощью следующего псевдокода:

let starting_time be an array of length n
current_time = 0
dfs(v):
	current_time = current_time + 1
	starting_time[v] = current_time
	shuffle children[v] randomly (each permutation with equal possibility)
	// children[v] is vector of children cities of city v
	for u in children[v]:
		dfs(u)

Как было сказано ранее, Барни начинает свое путешествие в корне дерева (что эквивалентно вызову dfs(1)).

Теперь Барни нужно собрать рюкзак, и поэтому он хочет знать больше о предстоящем путешествии: для каждого города i Барни хочет знать математическое ожидание величины starting_time[i]. Барни — друг Джона Сноу, и поэтому ничего не знает, в связи с чем просит вас ему помочь.