Rainbow Dragon Cave Tour

In the problem, the interior of Honglong Cave is abstracted as an undirected connected graph with $n$ vertices and $m$ edges. Note that the graph may contain self‐loops and multiple edges. Initially, Purple teleports Blue and Orange instantaneously to a starting vertex $S$. After the teleportation, Blue and Orange will move. In each unit of time, exactly one of the following moves is allowed:

1. Blue moves along an edge from her current vertex to an adjacent vertex.
2. Orange moves along an edge from his current vertex to an adjacent vertex.
3. Purple uses her power to swap the positions of Blue and Orange (this swap takes one unit of time as well).

Your task is to construct a plan (or itinerary) such that both Blue and Orange, individually, visit every vertex in the cave at least once and finally return to the starting vertex $S$.

The plan should be expressed in the following format:

• First, output an integer $k$ representing the total number of moves.
• Then output $k$ lines. Each line is one move in one of the following formats: • "B x" means Blue moves from her current vertex to an adjacent vertex $x$. • "O x" means Orange moves from his current vertex to an adjacent vertex $x$. • "P" means Purple swaps the positions of Blue and Orange.

It is guaranteed that the graph is connected, so a spanning tree exists. A simple solution is to perform a DFS on a spanning tree of the graph from $S$, which produces an Euler tour. You may use the Euler tour: [ \text{tour} = [S, v_1, S, v_2, \ldots, S]]

Then, execute the tour twice. In the first phase, let Blue follow the Euler tour while keeping Orange stationary at $S$. In the second phase, let Orange follow the same Euler tour while keeping Blue stationary at $S$. This ensures that both Blue and Orange visit all vertices at least once and eventually return to $S$.

inputFormat

The first line contains three integers $n$, $m$, and $S$, where $n$ is the number of vertices, $m$ is the number of edges, and $S$ is the starting vertex. Each of the following $m$ lines contains two integers $u$ and $v$, indicating that there is an undirected edge between $u$ and $v$.

outputFormat

First, output an integer $k$ — the total number of moves in your plan. Then output $k$ lines; each line must be one of the following commands:

• "B x": Blue moves from her current vertex to an adjacent vertex $x$. • "O x": Orange moves from his current vertex to an adjacent vertex $x$. • "P": Purple swaps the positions of Blue and Orange.

The moves must form a valid plan such that, by the end, both Blue and Orange have each visited every vertex at least once and both are back at the starting vertex $S$.

sample

1 0 1

0