Description

给定一棵有 $n$ 个节点的树， 节点从 $0$ 开始编号，$0$ 号点为根。初始时 $i$ 号点颜色为 $i$ 。

从一个点出发可以移动到与它有边相连的点，若两个点颜色不同则代价为 $1$ ，否则代价为 $0$ 。

接下来会有若干次操作，操作有两种：

1. 新增颜色操作：指定一个节点 $u$ ，将 $u$ 到根的路径上的所有节点的颜色，统一染为一个从未出现过的新颜色。

2. 询问操作：给定结点 $u$ ，询问以 $u$ 为根的子树内的所有结点，他们走到根结点（ $0$ 号点）的代价和的平均值。

现在请你给出每次询问的答案。

Input Format

第一行一个整数 $n$ ，表示树的结点数。

接下来 $n - 1$ 行，每行两个整数 $u$ ，$v$ 表示一条边。

接下来一行一个整数 $Q$ ， 表示接下来有 $Q$ 次操作，每次操作包括一个字符 $c$ 和一个整数 $u$。

若 $c$ 为小写字母 $\texttt{q}$ ，则表示询问以 $u$ 为根的子树中，所有结点代价和的平均值。

若 $c$ 为大写字母 $\texttt{O}$ ，则表示一次对点 $u$ 执行的新增颜色操作。

Output Format

对于每一次询问输出一行一个实数表示答案。答案与标准输出绝对误差不超过 $10 ^ {-6}$ 即算正确。

Sample

样例输入

13
0 1
0 2
1 11
1 10
1 9
9 12
2 5
5 8
2 4
2 3
4 6
4 7
7
q 0
O 4
q 6
q 2
O 9
q 9
q 2

样例输出

2.0000000000
1.0000000000
0.8571428571
0.5000000000
1.8571428571

Hint

$20 \%$ 的数据：$n, Q \leq 8000$

另有 $20 \%$ 的数据：树为随机生成

$70 \%$ 的数据：$n, Q \leq 50000$

$100 \%$ 的数据：$1 \leq n, Q \leq 150000$