Город Ф. представляет собой дерево. В нём поселился известный бандит, и сегодня верный полицейский решил во что бы то ни стало его поймать. Полицейский сильнее бандита, однако бандит гораздо быстрее первого. Поэтому преследование устроено так. В момент $$$t = 0$$$ полицейский оказывается в вершине с номером $$$s$$$, а бандит — в любой другой вершине дерева на его выбор. После этого они ходят по очереди, начиная с полицейского.
Отметим, что бандиту ещё неделю назад удалось прикрепить радиожучок к значку полицейского, поэтому бандиту в каждый момент известно местоположение полицейского (в частности, ему известен номер $$$s$$$). Напротив, полицейский ничего не знает о перемещениях бандита и сможет его обнаружить лишь в тот самый момент, когда его поймает.
Полицейский действует так, чтобы поймать бандита как можно раньше, а бандит — так, чтобы его поймали как можно позже. Поскольку погоню можно представить как игру с неполной информацией, участникам может быть выгодно использовать смешанные (вероятностные) стратегии — таким образом, полицейский действует так, чтобы минимизировать математическое ожидание продолжительности погони, а бандит — чтобы максимизировать.
Найдите математическое ожидание длительности погони при оптимальных действиях полицейского и бандита. Можно доказать, что оно всегда конечно (в частности, при оптимальных стратегиях вероятность того, что погоня будет продолжаться до бесконечности, равна нулю).
В первой строке находится целое число $$$n$$$ — количество вершин в дереве ($$$2 \leqslant n \leqslant 100$$$). В следующих $$$n - 1$$$ строках описывается город Ф.: каждая из них содержит пару целых чисел $$$u_i$$$, $$$v_i$$$ — номера концов очередного ребра ($$$1 \leqslant u_i, v_i \leqslant n$$$). Гарантируется, что эти рёбра образуют дерево.
В последней строке находится целое число $$$s$$$ — номер вершины, в которой изначально оказывается полицейский ($$$1 \leqslant s \leqslant n$$$).
Выведите одно вещественное число — математическое ожидание продолжительности погони при оптимальных стратегиях полицейского и бандита. Ваш ответ будет зачтён, если его абсолютная или относительная погрешность не превзойдёт $$$10^{-6}$$$; формально, если $$$p$$$ — ваш ответ, а $$$j$$$ — ответ жюри, должно выполняться $$$\frac{|p - j|}{\max\{1, |j|\}} \leqslant 10^{-6}$$$.
21 22
1
31 21 31
2
44 34 14 24
3.66667
71 44 55 24 66 77 33
8.3525
Ниже изображены деревья из примеров.