Background

Hackers reverse-engineered existing viruses, recombined many different viruses, and recompiled a new type of recombinant virus. This virus reproduces and mutates very quickly. To stop it from spreading, a security organization planned an experiment to study the virus.

Problem Description

The experiment is carried out in a closed LAN. There are $n$ computers in the LAN, numbered $1\sim n$. Some computers are directly connected by network cables, forming a tree structure.

There is a special computer in the LAN, called the core computer. Based on some preliminary research, the researchers designed an experiment with a total of $m$ steps. Before the experiment starts, the core computer is computer $1$. Each computer already contains one virus variant, and all variants are different. Each step of the experiment is one of the following operations:

• RELEASE x. Implant a new virus variant into computer $x$. This variant does not exist in the LAN before being implanted.
• RECENTER x. Change the core computer to computer $x$. However, this operation will cause the virus in the original core computer to produce a new variant and infect over. In other words, if the core computer before the operation is $y$, this is equivalent to additionally performing RELEASE y after the operation.

According to the research conclusion, when a new variant is implanted, the virus will search for the location of the core computer in the LAN, and infect along the shortest path in the network.

The first round of experiments revealed a shocking truth: different virus variants are mutually exclusive. When a new variant infects a computer that has already been infected by an old variant, it will completely destroy the old variant before infecting. But the researchers found a loophole in the process. If the new variant has not yet destroyed this kind of old variant during its infection process, it must first spend $1$ unit of time to analyze the old variant before it can destroy it. If it has destroyed this kind of old variant before, then destroying it can be considered to take no time. The transmission of the virus between two computers can also be considered to take no time.

The researchers are very interested in the total time cost of the whole infection process, because this is the best time to eliminate the virus. Therefore, during the $m$ steps of the experiment, the researchers sometimes make the following query:

• REQUEST x. Ask: if a new variant is implanted into a computer in the key set of computer $x$, what is the average infection time. A computer $y$ is in the key set of computer $x$ if and only if infecting from $y$ to the core computer along the shortest path must pass through $x$. Because of the RECENTER operation, this set is not necessarily always unchanged.

At this point, the security organization believes that an actual experiment is no longer needed, so they ask you to write a program to simulate the experiment results and answer all queries.

Input Format

The first line contains two integers $n$ and $m$, representing the number of computers in the LAN, and the total number of operations and queries.

The next $n-1$ lines each contain two integers $x$ and $y$, indicating that computers $x$ and $y$ are directly connected by a network cable.

The next $m$ lines each contain one operation or query, in the format described in the problem statement.

Output Format

For each query, output a real number representing the average infection time. The output is considered correct if the absolute error from the answer does not exceed $10^{-6}$.

8 6
1 2
1 3
2 8
3 4
3 5
3 6
4 7
REQUEST 7
RELEASE 3
REQUEST 3
RECENTER 5
RELEASE 2
REQUEST 1

4.0000000000
2.0000000000
1.3333333333

Hint

For $100\%$ of the testdata, $1\leq n\leq 10^5$ and $1\leq m\leq 10^5$.

Translated by ChatGPT 5