PEG Judge - NOI '07 - Thief Catching

National Olympiad in Informatics, China, 2007

Day 2, Problem 3 - Thief Catching

Magic Land has recently been troubled by the great thief Frank. Everywhere in Magic Land, Frank has been committing crimes. In particular, he is trying to steal various confidential files from government agencies (for this reason, people suspect that Frank is also a spy appointed by the enemy country). To capture Frank, Magic Land's security council has decided to carry out a firm offense!

Magic Land consists of N (1 ≤ N ≤ 1000) cities, and these N cities just happen to be connected by N−1 roads, in a fashion such that any city can reach any other city by traveling through some number of roads. From the structure of the data, we can also say that these N cities and N−1 roads form a tree.

For example, the following is one possible structure of Magic Land (4 cities labeled with numbers, 3 roads labeled with letters).

The great thief Frank can move at any speed along the roads. For example, regarding the structure above, in the time of 0.00001 seconds (or however small of a time frame), Frank can go from city 1, through city 2, and reach city 4, passing through two roads in the process.

Capturing Frank alive is an extremely difficult task, that's why the security council has appointed a group of highly experienced detectives. These detectives possess some extraordinary talents for capturing thieves:

As long as Frank and a detective are located in the same city, the detective will instantly take note and arrest him.
Even though Frank can move arbitrarily fast on roads, as long as a detective and Frank meet up on the same road, the detective will instantly discover and arrest him.

The security council does not know which city Frank is hiding in, nor which road that Frank is currently traveling on. So, they must develop a very thorough and extensive plan to capture him. The plan is made up of some number of steps. In each step, one of the following things are done:

Land a single detective by air onto a specific city. A detective from an aircraft can command to be dropped off at any city in Magic Land. This operation is denoted by "L x", indicating that the city numbered x will have one detective emplaced into it. The operation consumes 1 second.
Bring a single detective from a specific city back to headquarters. This makes preparations for future steps, in case a detective is needed in another city. This operation is denoted by "B x", indicating that one detective is recalled from the city numbered x. The operation consumes 1 second.
Have one detective located in city x move along a road to city y. This operation is denoted by "M x y", consuming 1 second. Of course, there is the precondition that a road must exist between city x and city y. If during the moving process, a detective and Frank are on the same road, then the detective will have captured him.

Your task now is to design a capturing plan, i.e. a series of steps, which guarantees that: no matter where Frank is located initially, and no matter how cunningly he moves (Frank may very well steal your actual plan to capture him, so he will definitely exhaust every possible method of escape), he will certainly be captured. Furthermore, you wish to use as few detectives as possible, because after all, highly experienced detectives are very hard to find.

Take the structure in the figure above for example. An acceptable plan is as follows:

L 2: Land a detective in city 2. Note that after this step, city 2 cannot contain Frank or else he would be captured.
L 2: Land another detective in city 2.
M 2 1: Move a detective from city 2 to city 1. Note that a detective still remains in city 2. After this step, city 1 cannot contain Frank and neither can road A. In other words, if Frank still has not been captured, then he can only be found in city 3, city 4, road B, or road C.
B 1: Bring back the detective in city 1. Note that although we've recalled this detective, there still remains a detective on guard in city 2. So, Frank still cannot run back to city 1 or onto road A.
L 3: Land a detective in city 3. Note that this operation can use the detective we've brought back in the previous step. After this step, city 3 cannot contain Frank or else would be captured.
M 3 2: Move the detective from city 3 to city 2. After this step, if Frank still has not been captured, then he must be on road C or in city 4. Note that after this step, city 2 will contain two detectives.
M 2 4: Move a detective from city 2 to city 4. Frank will certainly be caught after this step, unless he has not come to Magic Land in the first place.

This plan makes use of a total of 2 detectives. If a plan uses only 1 detective from start to finish, then it's guaranteed that Frank will just roam wild.

Your task is simple: for a given structure of Magic Land, calculate S, the minimum number of detectives required to catch Frank, while also providing the corresponding plan to do so.

Input Format

The input will contain the structure of Magic Land.
The first line of input contains a single integer N, indicating that there are N cities labeled from 1 to N.
The following N−1 lines each contain a pair of space-separated integers x_i and y_i, indicating that cities x_i and y_i are connected, where 1 ≤ x_i, y_i ≤ N.

Output Format

The output should contain your plan for catching Frank.
On the first line, please output a single integer S, the minimum number of detectives required.
On the second line, please output a single integer T, the total number of steps in your plan.
Please output T lines afterwards, each line describing a step of the plan. Each line must be one of the three formats below:

"L x" – that is, an uppercase L, following by a space, followed by an integer x, indicating that a detective is to be landed in city x. You must ensure that 1 ≤ x ≤ N.
"B x" – that is, an uppercase B, following by a space, followed by an integer x, indicating that a detective from city x is to be brought back to headquarters. You must ensure that 1 ≤ x ≤ N, and that before making this command, there is at least one detective in city x.
"M x y" – that is, an uppercase B, following by a space, followed by an integer x, followed by another space, finally followed by an integer y. This moves a detective from city x to city y. You must ensure that 1 ≤ x, y ≤ N, city x contains at least one detective, and that a road exists between city x and city y.

You must also ensure that S matches the number of detectives used in your plan.

Sample Input

Sample Output

Scoring

For each test case: if your plan is invalid, or the total number of steps T in your plan exceeds 20000, or Frank is not guaranteed to be caught after your plan, then your score is zero.

Otherwise, your score for the test case will be determined by comparing your outputted value of S and our known and accurate answer of S*: