Catching Frank in Magic Land

In Magic Land, there are N cities connected by exactly N-1 roads, forming a tree. A notorious thief, Frank, roams the roads at arbitrarily high speeds and escapes capture by cunningly choosing his routes. The security bureau has devised a set of operations to guarantee Frank’s capture regardless of his starting position or movements. However, to preserve the limited pool of experienced detectives, they want to use as few detectives as possible.

There are three kinds of operations, each taking 1 second:

• L x: Air drop a detective into city x.
• B x: Recall the detective stationed in city x back to headquarters.
• M x y: Move a detective from city x to an adjacent city y (there must be a direct road between x and y). If Frank is anywhere on that road at that time, he will be caught.

The overall plan is a sequence of these operations. A detective catches Frank immediately if they are in the same city at the end of any step, or if they meet Frank on a road during a move. Frank may start anywhere in Magic Land and can arbitrarily choose his movement path (even knowing the complete plan).

Your task is to compute S — the minimum number of detectives that are concurrently required to guarantee Frank’s capture — and output a valid plan (i.e. a sequence of operations) that ensures capture regardless of Frank’s strategy.

Observation:

• If N = 1, then one detective (S = 1) is enough.
• If N = 2, one detective (S = 1) suffices by dropping him at one city and moving him to the other.
• If N ≥ 3, it can be shown that at least 2 detectives are required. One possible strategy is to choose a root (preferably a vertex with degree at least 2) and perform a depth-first search (DFS) of the tree using two detectives: one always remains as a guard in the cleared region while the other moves to clear the adjacent branch. The operations for moving are generated as follows:

For each edge (u, v) traversed in the DFS:
   1. Drop an extra detective in u: "L u"
   2. Move a detective from u to v: "M u v"
   3. Recursively clear the subtree rooted at v (ignoring u), using the same strategy.
   4. Once cleared, move the detective back from v to u: "M v u"
   5. Recall the detective from v: "B v"

In the main routine, a detective is first dropped at the chosen root. Then, for each neighbor v of the root, the above procedure is performed. At the end of the plan the guard detective remains in the root city, having cleared all branches.

Input and Output specifications follow.

inputFormat

The input begins with a single integer N (1 ≤ N ≤ 10⁵), the number of cities. Each of the next N-1 lines contains two integers u and v (1 ≤ u, v ≤ N), denoting that there is a road directly connecting cities u and v. It is guaranteed that the cities form a tree.

outputFormat

On the first line, output an integer S, the minimum number of detectives that must be concurrently involved. On the second line, output an integer K, the total number of operations in your plan. Each of the following K lines should contain one operation in the format described (L x, B x, or M x y). The plan must guarantee that Frank is caught regardless of his actions.

sample

1

1
1
L 1