Description

A notorious thief named Frank has recently appeared in the magical kingdom Magic Land. He commits crimes all over Magic Land, specializing in stealing confidential government documents (so some suspect Frank is a spy sent by an enemy nation).

To capture Frank, the Security Bureau of Magic Land is taking strong action!

Magic Land consists of $N$ cities, and these $N$ cities are connected by exactly $N-1$ roads so that any two cities can be reached via some sequence of roads. From a data structure perspective, these $N$ cities and $N-1$ roads form a tree.

For example, the following diagram shows one possible layout of Magic Land ($4$ cities labeled with numbers, $3$ roads labeled with letters):

Frank can move along roads at any speed.

For instance, in the layout above, within $0.00001$ seconds (or any arbitrarily short period of time), Frank can go from city $1$ through city $2$ to city $4$, passing along two roads.

Capturing Frank alive is extremely difficult, so the Bureau has dispatched experienced detectives with exceptional pursuit skills:

1. If a detective and Frank are in the same city, the detective immediately detects Frank and arrests him.
2. Although Frank can move arbitrarily fast along roads, if a detective and Frank meet on the same road, the detective can also immediately detect Frank and arrest him.

The Bureau has no idea which city Frank is hiding in, nor on which road he might be moving, so they must devise a meticulous capture plan consisting of several steps. In each step, exactly one of the following actions can be performed:

1. Airdrop a detective into some city. A detective can be airdropped directly from headquarters into any city in Magic Land. This operation is denoted as L x, meaning a detective is airdropped into city $x$. It takes $1$ second.
2. Recall a detective who is staying in some city back to headquarters, to be available for later airdrop into some city. This operation is denoted as B x, meaning a detective in city $x$ is recalled to headquarters. It takes $1$ second.
3. Move a detective in city $x$ along a road to city $y$. This operation is denoted as M x y. It takes $1$ second. Of course, this requires that there is a road between cities $x$ and $y$. If, during the detective’s move, Frank is also on the same road, then the detective will capture Frank.

Now it is your turn to devise a capture plan, i.e., to output a sequence of steps, ensuring that no matter where Frank initially hides and no matter how cunningly he moves throughout the process (Frank might steal the plan, so he will try every means to evade capture), he is guaranteed to be apprehended.

We want to use as few detectives as possible, since experienced detectives are scarce.

For the layout shown earlier, one feasible plan is as follows:

1. L 2: Airdrop a detective into city $2$. Note that after this step is completed, Frank cannot be in city $2$, otherwise he would have been captured.
2. L 2: Airdrop another detective into city $2$.
3. M 2 1: Move one detective from city $2$ to city $1$. Note that another detective remains in city $2$. After this step, Frank cannot be in city $1$, nor on road $A$. In other words, if Frank has not been arrested yet, he can only be in city $3$ or city $4$, or on road $B$ or road $C$.
4. B 1: Recall the detective in city $1$. Note that although this detective is recalled, since we have kept a detective guarding city $2$ the whole time, Frank still cannot get to city $1$ or road $A$.
5. L 3: Airdrop a detective into city $3$. Note that this step can airdrop the detective who was recalled earlier. After this step is completed, Frank cannot be in city $3$, otherwise he would be captured.
6. M 3 2: Move a detective from city $3$ to city $2$. After this step, if Frank has still not been captured, then he can only be on road $C$ or in city $4$. Note that after this step there are two detectives in city $2$.
7. M 2 4: Move a detective from city $2$ to city $4$. After this step, Frank is guaranteed to be captured, unless he never came to Magic Land at all.

This plan requires a total of $2$ detectives. It can be proved that if at all times only $1$ detective (or fewer) participates, Frank will escape.

Your task is simple: for a given layout of Magic Land, compute $S$, the minimum number of detectives required to capture Frank, and output a corresponding capture plan.

Input Format

The input file gives the layout of Magic Land.

The first line contains an integer $N$, the number of cities, numbered $1$ to $N$.

The next $N-1$ lines each contain two integers $x_i,y_i$ separated by a space, indicating that cities $x_i$ and $y_i$ are connected by a road. It is guaranteed that $1\le x_i,y_i \le N$.

Output Format

Output your capture plan.

On the first line, output an integer $S$, the number of detectives required by your plan.

On the second line, output an integer $T$, the total number of steps in your plan.

Then output $T$ lines, each describing one step of the plan. Each line must be in one of the following three forms:

L x, where L is an uppercase letter, followed by a space, then an integer $x$, meaning a detective is airdropped into city $x$. You must ensure $1\le x\le N$.

B x, where B is an uppercase letter, followed by a space, then an integer $x$, meaning a detective in city $x$ is recalled. You must ensure $1\le x\le N$, and that prior to this step, there is indeed at least one detective in city $x$.

M x y, where M is an uppercase letter, followed by a space, then an integer $x$, followed by a space, and finally an integer $y$, meaning a detective in city $x$ moves along a road to city $y$. You must ensure $1\le x,y\le N$, that prior to this step there is indeed at least one detective in city $x$, and that there is a road between cities $x$ and $y$.

You must ensure that the output $S$ is exactly the number of detectives used by your plan.

4
1 2
3 2
2 4

2
7
L 2
L 2
M 2 1
B 1
L 3
M 3 2
M 2 4

Hint

For any test point:

If the output plan is invalid, or the total number of steps $T$ exceeds $20000$, or after the plan ends Frank is not guaranteed to be captured, you will receive no points.

Otherwise, compare your output $S$ with our known optimal answer $S ^*$:

1. If $S<S ^*$, you get $120\%$ of the points.
2. If $S=S ^*$, you get $100\%$ of the points.
3. If $S ^* <S \le S ^* +2$, you get $60\%$ of the points.
4. If $S ^* +2<S \le S ^* +4$, you get $40\%$ of the points.
5. If $S ^* +4<S \le S ^* +8$, you get $20\%$ of the points.
6. If $S>S ^* +8$, you get $10\%$ of the points.

The input is guaranteed to describe a connected tree with $N$ nodes, $1 \le N \le 1000$.

Translated by ChatGPT 5