F. Сжимающееся дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим дерево $$$T$$$ (связный неориентированный граф без циклов) с $$$n$$$ вершинами, пронумерованными целыми числами от $$$1$$$ до $$$n$$$. Запустим следующий процесс на $$$T$$$: пока в $$$T$$$ более одной вершины, делать следующее:

  • равновероятно выбрать случайное ребро $$$T$$$;
  • стянуть выбранное ребро: если ребро соединяло вершины $$$v$$$ и $$$u$$$, удалить и $$$v$$$, и $$$u$$$, и создать новую вершину, смежную со всеми вершинами, которые до этого были смежны или с $$$v$$$, или с $$$u$$$. Новая вершина равновероятно получает номер или $$$v$$$, или $$$u$$$.

Когда процесс завершится, $$$T$$$ будет состоять из одной вершины, с номером из $$$1, \ldots, n$$$. Найдите для каждого числа вероятность, что это число окажется номером финальной вершины.

Входные данные

В первой строке входного файла записано целое число $$$n$$$ ($$$1 \leq n \leq 50$$$).

Следующие $$$n - 1$$$ строк описывают ребра дерева. Каждая из этих строк содержит два целых числа $$$u_i, v_i$$$ — номера вершин, соединенных соответствующим ребром ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$). Гарантируется, что данный граф является деревом.

Выходные данные

Выведите $$$n$$$ вещественных чисел — описанные вероятности для номеров $$$1, \ldots, n$$$, соответственно. Все числа должны быть правильными с точностью до абсолютной или относительной погрешности $$$10^{-6}$$$.

Примеры
Входные данные
4
1 2
1 3
1 4
Выходные данные
0.1250000000
0.2916666667
0.2916666667
0.2916666667
Входные данные
7
1 2
1 3
2 4
2 5
3 6
3 7
Выходные данные
0.0850694444
0.0664062500
0.0664062500
0.1955295139
0.1955295139
0.1955295139
0.1955295139
Примечание

В первом примере, получившаяся вершина будет иметь номер 1 тогда и только тогда, когда для всех ребер вершина 1 выживет, соответственно вероятность равна $$$1/2^3 = 1/8$$$. Все остальные числа имеют равную вероятность из-за симметрии, таким образом, каждое из них имеет вероятность $$$(1 - 1/8) / 3 = 7/24$$$.