星球大战
题号：NC54342
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述

Y星球是一个美丽富饶的星球，然而最近它收到了来自X星人的攻击。为了能够抵御X星人，Y星人正在努力修建碉堡。
Y星球一开始只有一座碉堡该碉堡标号为1，以后每次Y星人会修建一个碉堡，该碉堡的标号为已经存在的碉堡的最大标号+1，并修建一条由fa_x通向新建碉堡的长度为1的单向道路。
每个碉堡都会有一些命令需要向其他碉堡传达。由于道路是有方向的，所以显然这些命令的传递也是有方向的。X星人的攻击方式很特别，具体的讲，他们每次会攻击一个碉堡，使得所有可以传递该碉堡发出的命令的道路有的概率损坏。
为了更好的建设碉堡，Y星球球长每次会告诉你他新建了一座新的碉堡并且修建了由fa_x连向这座新碉堡的道路。或者询问当x碉堡被攻击时。你从碉堡x开始命令期望传达的最远距离。
因为Y星人恢复能力极强所以前面的攻击并不会影响后面的询问。

输入描述:

第一行两个整数，T，Q分别表示测试点编号和操作或询问的数量。样例文件中的T为0。
以后Q行，每行两个整数opt,x。
如果opt=1表示新建一个节点，并由标号为x的碉堡向新建碉堡连接一条单向道路，保证x为已经存在的碉堡。
如果opt=2表示询问当X星人攻击x碉堡时，x碉堡发出的令命期望传递的最远距离。

输出描述:

对于每个opt=2的询问，你需要回答一个实数。

如果你的答案与标准答案的绝对误差或相对误差不超过即被视为正确。形式化的讲，如果你的答案为x,标准答案为y。答案正确当且仅当
示例1

输入

复制 
0 7 
1 1 
1 1
2 1
1 2 
1 3 
2 2 
2 1

输出

复制 
0.7500000000
0.5000000000
1.1875000000

说明

第一次询问时碉堡网络的形态如下图。



所有可能被成功损坏的道路情况及其答案分别为:
{\emptyset}:1
{1}:1
{2}:1
{1,2}:0
所有情况概率均为\frac{1}{4}，所以期望传递长度为\frac{1+1+1+0}{4}=0.75

第二和第三次询问时碉堡形态如下图。



当攻击2号点时所有可能被成功损坏的道路情况及其答案分别为:
{\emptyset}:1
{3}:0
每种情况概率为\frac{1}{2}，所以期望最长传递长度为\frac{1}{2}=0.5
当攻击1号点时所有可能被成功损坏的道路情况及其答案分别为:
{\emptyset}:2
{1}:2
{3}:2
{2}:2
{4}:2
{1,2}:0
{1,3}:2
{1,4}:1
{2,3}:1
{2,4}:2
{3,4}:1
{1,2,3}:0
{1,2,4}:0
{1,3,4}:1
{2,3,4}:1
{1,2,3,4}:0
每种情况的概率均为\frac{1}{2^4}，所以期望传递的最长长度为\frac{2\times 7+1\times5}{16}=1.1875

备注:

m表示2操作的数量，H为最终1号点命令能传递的最大距离。
性质1：所有事件2在事件1之后
性质2：