National Olympiad in Informatics, China, 2007
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 cities, and these cities just happen to be connected by 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 cities and roads form a tree.
For example, the following is one possible structure of Magic Land ( cities labeled with numbers, 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 seconds (or however small of a time frame), Frank can go from city , through city , and reach city , 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 will have one detective emplaced into it. The operation consumes 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 . The operation consumes second. - Have one detective located in city move along a road to city
. This operation is denoted by
M x y
, consuming second. Of course, there is the precondition that a road must exist between city and city . 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 . Note that after this step, city cannot contain Frank or else he would be captured.L 2
: Land another detective in city .M 2 1
: Move a detective from city to city . Note that a detective still remains in city . After this step, city cannot contain Frank and neither can road . In other words, if Frank still has not been captured, then he can only be found in city , city , road , or road .B 1
: Bring back the detective in city . Note that although we've recalled this detective, there still remains a detective on guard in city . So, Frank still cannot run back to city or onto road .L 3
: Land a detective in city . Note that this operation can use the detective we've brought back in the previous step. After this step, city cannot contain Frank or else would be captured.M 3 2
: Move the detective from city to city . After this step, if Frank still has not been captured, then he must be on road or in city . Note that after this step, city will contain two detectives.M 2 4
: Move a detective from city to city . 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 detectives. If a plan uses only 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 , the minimum number of detectives required to catch Frank, while also providing the corresponding plan to do so.
Input Specification
The input will contain the structure of Magic Land.
The first line of input will contain a single integer , indicating that
there are cities labeled from to .
The following lines each contain a pair of space-separated
integers and , indicating that cities and
are connected, where .
Output Specification
The output should contain your plan for catching Frank.
On the first line, please output a single integer , the minimum
number of detectives required.
On the second line, please output a single integer , the total number
of steps in your plan.
Please output 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 , followed by a space, followed by an integer , indicating that a detective is to be landed in city . You must ensure that .B x
– that is, an uppercase , followed by a space, followed by an integer , indicating that a detective from city is to be brought back to headquarters. You must ensure that , and that before making this command, there is at least one detective in city .M x y
– that is, an uppercase , followed by a space, followed by an integer , followed by another space, finally followed by an integer . This moves a detective from city to city . You must ensure that , city has at least one detective, and that a road exists between city and city .
You must also ensure that matches the number of detectives used in your plan.
Sample Input
4
1 2
3 2
2 4
Sample Output
2
7
L 2
L 2
M 2 1
B 1
L 3
M 3 2
M 2 4
Scoring
For each test case: if your plan is invalid, or the total number of steps in your plan exceeds , 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 and our known and accurate answer of :
- If , then you will score of points.
- If , then you will score of points.
- If , then you will score of points.
- If , then you will score of points.
- If , then you will score of points.
- If , then you will score of points.
Problem translated to English by .
Comments