Бешеная погоня
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Город Ф. представляет собой дерево. В нём поселился известный бандит, и сегодня верный полицейский решил во что бы то ни стало его поймать. Полицейский сильнее бандита, однако бандит гораздо быстрее первого. Поэтому преследование устроено так. В момент $$$t = 0$$$ полицейский оказывается в вершине с номером $$$s$$$, а бандит — в любой другой вершине дерева на его выбор. После этого они ходят по очереди, начиная с полицейского.

Отметим, что бандиту ещё неделю назад удалось прикрепить радиожучок к значку полицейского, поэтому бандиту в каждый момент известно местоположение полицейского (в частности, ему известен номер $$$s$$$). Напротив, полицейский ничего не знает о перемещениях бандита и сможет его обнаружить лишь в тот самый момент, когда его поймает.

Полицейский действует так, чтобы поймать бандита как можно раньше, а бандит — так, чтобы его поймали как можно позже. Поскольку погоню можно представить как игру с неполной информацией, участникам может быть выгодно использовать смешанные (вероятностные) стратегии — таким образом, полицейский действует так, чтобы минимизировать математическое ожидание продолжительности погони, а бандит — чтобы максимизировать.

Найдите математическое ожидание длительности погони при оптимальных действиях полицейского и бандита. Можно доказать, что оно всегда конечно (в частности, при оптимальных стратегиях вероятность того, что погоня будет продолжаться до бесконечности, равна нулю).

Input

В первой строке находится целое число $$$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$$$).

Output

Выведите одно вещественное число — математическое ожидание продолжительности погони при оптимальных стратегиях полицейского и бандита. Ваш ответ будет зачтён, если его абсолютная или относительная погрешность не превзойдёт $$$10^{-6}$$$; формально, если $$$p$$$ — ваш ответ, а $$$j$$$ — ответ жюри, должно выполняться $$$\frac{|p - j|}{\max\{1, |j|\}} \leqslant 10^{-6}$$$.

Examples

Input
2
1 2
2
Output
1
Input
3
1 2
1 3
1
Output
2
Input
4
4 3
4 1
4 2
4
Output
3.66667
Input
7
1 4
4 5
5 2
4 6
6 7
7 3
3
Output
8.3525

Note

Ниже изображены деревья из примеров.