310945: CF1912F. Fugitive Frenzy

F. Fugitive Frenzytime limit per test5 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

The city of F. can be represented as a tree. A famous fugitive is hiding in it, and today a faithful police officer decided to catch him at all costs. The police officer is stronger than the fugitive, but the fugitive is much faster than the former. That is why the pursuit proceeds as follows. At the moment $t = 0$ the police officer appears at the vertex with number $s$, and the fugitive spawns at any other vertex of his choice. After that, they take turns, starting with the police officer.

• During the police officer's move, she selects any vertex adjacent to the one where she is currently located and moves there. The police officer spends one minute moving. Also, the police officer may decide to stand still instead, in which case she waits one minute at the vertex at which she started her move. If at the end of the turn the police officer ends up at the same vertex as the fugitive, she instantly catches him and the chase ends.
• The fugitive's move is as follows. Let him be at vertex $b$, and the police officer at vertex $p$. Then the fugitive chooses any vertex $b' \ne p$ such that the path between the vertices $b$ and $b'$ does not contain vertex $p$ and instantly moves there. In particular, he can always choose $b' = b$ to stay where he is. The fugitive's move takes no time.

Note that the fugitive managed to attach a radio bug to the police officer's badge a week ago, so the fugitive knows the location of the police officer at every moment (in particular, he knows the number $s$). On the contrary, the police officer knows nothing about the fugitive's movements and will only be able to detect him at the very moment she catches him.

The police officer aims to catch the fugitive as fast as possible, and the fugitive aims to be caught as late as possible. Since the chase can be thought of as a game with incomplete information, participants can use mixed (probabilistic) strategies — thus, the police officer acts to minimize the expected duration of the chase, and the fugitive — to maximize it.

Find the mathematical expectation of the duration of the chase with optimal actions of the police officer and the fugitive. It can be proven that it is always finite. In particular, with optimal strategies, the probability that the chase continues indefinitely is equal to zero.

Input

The first line contains an integer $n$ — the number of vertices in the tree ($2 \le n \le 100$). The next $n - 1$ lines describe the city of F.: each of them contains a pair of integers $u_i$, $v_i$ — the numbers of the ends of an edge ($1 \le u_i, v_i \le n$). These edges are guaranteed to form a tree.

The last line contains an integer $s$ — the number of the vertex where the police officer initially appears ($1 \le s \le n$).

Output

Print one real number — the mathematical expectation of the duration of the chase with the optimal strategies of the police officer and the fugitive. Your answer will be accepted if its absolute or relative error does not exceed $10^{-6}$; formally, if $p$ is your answer, and $j$ is the jury's answer, this should hold: $\frac{|p - j|}{\max\{1, |j|\}} \le 10^{-6}$.

ExamplesInput

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

The trees from the examples are depicted below.

题目大意：
题目描述了一个警察追捕逃犯的游戏。游戏发生在一个城市的树上，警察和逃犯分别在不同的顶点上。警察每次可以移动到相邻的顶点，或者选择原地不动。逃犯知道警察的位置，可以在不经过警察所在顶点的情况下，瞬间移动到树上的任意其他顶点。游戏的目标是求出在最优策略下，警察抓到逃犯的期望时间。

输入数据格式：
第一行包含一个整数n，表示树的顶点数（2≤n≤100）。接下来的n-1行，每行包含两个整数ui和vi，表示树的一条边（1≤ui,vi≤n）。最后一行包含一个整数s，表示警察初始所在的顶点（1≤s≤n）。

输出数据格式：
输出一个实数，表示在最优策略下，警察抓到逃犯的期望时间。你的答案的绝对或相对误差不超过10^-6时视为正确。

示例：
输入：
2
1 2
2
输出：
1

输入：
3
1 2
1 3
1
输出：
2

输入：
4
4 3
4 1
4 2
4
输出：
3.66667

输入：
7
1 4
4 5
5 2
4 6
6 7
7 3
3
输出：
8.3525题目大意： 题目描述了一个警察追捕逃犯的游戏。游戏发生在一个城市的树上，警察和逃犯分别在不同的顶点上。警察每次可以移动到相邻的顶点，或者选择原地不动。逃犯知道警察的位置，可以在不经过警察所在顶点的情况下，瞬间移动到树上的任意其他顶点。游戏的目标是求出在最优策略下，警察抓到逃犯的期望时间。 输入数据格式： 第一行包含一个整数n，表示树的顶点数（2≤n≤100）。接下来的n-1行，每行包含两个整数ui和vi，表示树的一条边（1≤ui,vi≤n）。最后一行包含一个整数s，表示警察初始所在的顶点（1≤s≤n）。 输出数据格式： 输出一个实数，表示在最优策略下，警察抓到逃犯的期望时间。你的答案的绝对或相对误差不超过10^-6时视为正确。 示例： 输入： 2 1 2 2 输出： 1 输入： 3 1 2 1 3 1 输出： 2 输入： 4 4 3 4 1 4 2 4 输出： 3.66667 输入： 7 1 4 4 5 5 2 4 6 6 7 7 3 3 输出： 8.3525