Description

树之大陆是一个有 N 座城市的王国（城市从 0 开始编号）。

城市之间有 N-1 条道路连接，使得两点之间恰好有一条道路。

城市 0 为首都。

初始时每个城市都会被一个不用的帮会所控制。村民在相邻的城市间移动，如果这两个城市不属于桶一个帮会的势力范围内，那么需要支付一个单位的代价。每一年都会有一个新的帮会涌入首都，它们会扩张自己的势力范围。

具体的说，它们会占据从首都到 u 路径上所有城市，（包括首都和 u ）。

因为这个原因，来往与城市间的代价变得琢磨不定，这让村民很苦恼，于是它们找你来帮忙。

给定一个城市 u，请你勾出以 u 为根的子树中，所有节点到根节点的代价的平均值。

Input

第一行输入 N。表示 N 个城市。

第 2~N 行，每行输入 u,v，表示一条连接 u,v 的边。

第 N+1 行输入 Q。表示有 Q 个询问。

接下来有 Q 组操作，每个操作包括一个字符 c，一个整数 u

若 c='q'，表示询问以 u 为根的子树中，所有节点到根节点的代价的平均值。

若 c='O'，表示有一个新的帮会占据了从 u 到首都路径上的所有城市。

Output

对于每一组询问，输出答案。（当你的答案与标程之差的绝对值 <1e-6 将被视为正确）

Samples

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

Limitation

20%的数据满足N,Q<=8000

还有20%的数据满足树为随机生成。

70%的数据满足N,Q<=50000

100%的数据满足N,Q<=150000