A9761 | ELCA

You have a root tree containing $n$ vertexes. Let's number the tree vertexes with integers from $1$ to $n$ . The tree root is in the vertex $1$ .

Each vertex (except fot the tree root) $v$ has a direct ancestor $p_{v}$ . Also each vertex $v$ has its integer value $s_{v}$ .

Your task is to perform following queries:

- P $v$ $u$ ( $u≠v$ ). If $u$ isn't in subtree of $v$ , you must perform the assignment $p_{v}=u$ . Otherwise you must perform assignment $p_{u}=v$ . Note that after this query the graph continues to be a tree consisting of $n$ vertexes.
- V $v$ $t$ . Perform assignment $s_{v}=t$ .

Your task is following. Before starting performing queries and after each query you have to calculate expected value written on the lowest common ancestor of two equiprobably selected vertices $i$ and $j$ . Here lowest common ancestor of $i$ and $j$ is the deepest vertex that lies on the both of the path from the root to vertex $i$ and the path from the root to vertex $j$ . Please note that the vertices $i$ and $j$ can be the same (in this case their lowest common ancestor coincides with them).

You have a root tree containing $n$ vertexes. Let's number the tree vertexes with integers from $1$ to $n$ . The tree root is in the vertex $1$ .

Each vertex (except fot the tree root) $v$ has a direct ancestor $p_{v}$ . Also each vertex $v$ has its integer value $s_{v}$ .

Your task is to perform following queries:

- P $v$ $u$ ( $u≠v$ ). If $u$ isn't in subtree of $v$ , you must perform the assignment $p_{v}=u$ . Otherwise you must perform assignment $p_{u}=v$ . Note that after this query the graph continues to be a tree consisting of $n$ vertexes.
- V $v$ $t$ . Perform assignment $s_{v}=t$ .

Your task is following. Before starting performing queries and after each query you have to calculate expected value written on the lowest common ancestor of two equiprobably selected vertices $i$ and $j$ . Here lowest common ancestor of $i$ and $j$ is the deepest vertex that lies on the both of the path from the root to vertex $i$ and the path from the root to vertex $j$ . Please note that the vertices $i$ and $j$ can be the same (in this case their lowest common ancestor coincides with them).

Print $q+1$ number — the corresponding expected values. Your answer will be considered correct if its absolute or relative error doesn't exceed $10^{-9}$ .