题目描述

给定一个初始以 $1$ 为根的树，每个结点 $i$ 初始有颜色 $c_i=i$。定义一次结点 $x$ 的「交流」为，将 $x$ 到当前根的路径上的结点颜色都改为一种从未出现过的颜色，你可以认为第 $i$ 次交流产生的新颜色的编号为 $n+i$。

你需要支持 $q$ 次如下操作：

• Make_Root x：记当前的根为 $u$，则把根替换为 $x$ 后并对 $u$ 进行一次交流；
• Paint x：对结点 $x$ 进行一次交流；
• Query x：询问 $x$ 的子树中所有点到根的路径上平均有多少种颜色，保留 $7$ 位小数。

输入格式

第一行两个正整数 $n,q$。

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

接下来 $q$ 行，每行一个操作，格式见题目描述。

输出格式

对于每个询问，输出一行一个实数表示答案，保留 $7$ 位小数。

8 6
1 2
1 3
2 8
3 4
3 5
3 6
4 7
Query 7
Paint 3
Query 3
Make_Root 5
Paint 2
Query 1

4.0000000
2.0000000
1.3333333

数据规模与约定

对于 $100\%$ 的数据，$1\leq n,q\leq 10^5$。