Background

Note that the meanings of the commands in this problem are slightly different from those in the preliminary round.

Problem Description

There are $n$ robots standing in a circle, numbered $0 \sim n-1$ in counterclockwise order.

Each robot has two hands. Initially, for robot $i$, its “left hand” points to robot $l_i$, and its “right hand” points to robot $r_i$.

Inside every robot, there is a “command”. The “commands” can have the following forms.

Commands

Below we describe the format of these “commands” and their effects when being “executed”. In the statements below, the word “itself” always refers to the robot that owns this “command”.

• SLACKOFF: “slack off”, i.e. do nothing.
• MOVE h z: Move the $h$-th hand counterclockwise by $z$ robots. When $h=0$, it means the “left hand”; when $h=1$, it means the “right hand”. The same applies below.
• SWAP: Swap the “commands” of the two robots that its hands point to.
• TRIGGER <COMMANDNAME>: <COMMAND>: Here, <COMMANDNAME> is one of SLACKOFF, MOVE, SWAP, TRIGGER, TOGGLETRIGGERREPLACE; <COMMAND> is a complete non-TRIGGER “command”. The TRIGGER command itself will not be “executed”. However, when some other robot finishes “executing” a “command”, and its “right hand” points to itself, then its TRIGGER command (if any) that satisfies the following conditions will be “triggered”, meaning that the corresponding <COMMAND> will be “executed” once:
  • If <COMMANDNAME> is not TRIGGER, then the “command” that has just been executed is a <COMMANDNAME> command;
  • If <COMMANDNAME> is TRIGGER, then the “command” that has just been executed is the <COMMAND> part executed when a TRIGGER command is “triggered”.
• TOGGLETRIGGERREPLACE h <COMMANDNAME> <NEWCOMMAND>: If the “command” of the robot pointed to by the $h$-th hand is a TRIGGER command, then “toggle” it into the <COMMAND> part of that “command”, i.e. delete the leading TRIGGER and its condition part. If that “command” is not a TRIGGER command, suppose it is <COMMAND>, then toggle it into TRIGGER <COMMANDNAME>: <COMMAND>. Here, <COMMANDNAME> is one of SLACKOFF, MOVE, SWAP, TRIGGER, TOGGLETRIGGERREPLACE. Then modify its own “command” (note that this may include more than just the part currently being “executed”) into <NEWCOMMAND>, where <NEWCOMMAND> is a complete “command”.

The output format when robots “execute” commands is as follows:

• When “slacking off”, output Robot <id> slacks off. where <id> is an integer denoting the id of the robot “executing” the current “command”. The same applies below.
• When “moving”, output Robot <id> moves its <side> hand towards Robot <id2>. where <side> is left or right, indicating which hand is moved (left for “left hand”, right for “right hand”); <id2> is an integer denoting the id of the robot that this hand points to after moving.
• When “swapping”, output Robot <id> swaps the commands of Robot <id2> and Robot <id3>. where <id2> and <id3> are integers denoting the ids of the robots whose “commands” are “swapped”. These two numbers may be output in any order.
• When “toggling”, output Robot <id> toggles the trigger property of the command of Robot <id2>.
• TRIGGER commands will not be “executed”, but when they are “triggered”, the corresponding “command” will be “executed” and output in the formats above.

You selected some robots in a certain order (robots may be selected repeatedly) and “executed” their “commands”, obtaining the complete output of “execution”. That is, after the last “command” in the output is executed, no other “command” is “triggered”. However, you forgot the order in which you selected robots, and you also forgot what “command” each robot initially had. You only remember the total number of robots and where each robot’s hands initially point.

You want to recover what the initial “command” of every robot was using all the known information.

Input Format

The first line contains two positive integers $n,k$, where $k$ is the total number of output lines.

The next $n$ lines each contain two integers $l_i,r_i$, given in increasing order of robot id.

The next $k$ lines each contain one output message of an “executed” “command”.

To reduce the burden of processing input, the output messages are simplified as follows (unless otherwise specified, the meanings of parameters are the same as above):

• When “slacking off”, output SLACKOFF <id>.
• When “moving”, output MOVE <id> <side> <id2>, where <side> is 0 or 1, indicating which hand is moved (0 for “left hand”, 1 for “right hand”).
• When “swapping”, output SWAP <id> <id2> <id3>.
• When “toggling”, output TOGGLETRIGGERREPLACE <id> <id2>.
• TRIGGER commands will not be “executed”, but when they are “triggered”, the corresponding “command” will be “executed” and output in the formats above.

The input guarantees that there exists a set of initial “commands” such that there is a way to select robots to obtain the given output.

Constraints: $1\le n,k \le 500000$.

Also, $0\le l_i,r_i<n$ is guaranteed.

Output Format

Output $n$ lines. Print the initial “command” of each robot in increasing order of robot id, one per line.

You must ensure that the “command” format is correct, and that $0\le z < n$.

You must ensure that your output file is not too large. If your output file size does not exceed $100\texttt{MB}$, then Special Judge is guaranteed to return the result correctly.

In addition, any answer that can produce the $k$ lines of output in the input is considered correct.

4 7
1 3
2 0
3 0
2 1
SWAP 1 0 2
SWAP 0 1 3
SWAP 1 2 0
MOVE 0 0 2
SWAP 1 0 2
SWAP 0 2 3
MOVE 3 0 3

MOVE 0 1
SWAP
TRIGGER SWAP: SWAP
SWAP

4 7
1 2
2 3
3 1
0 2
TOGGLETRIGGERREPLACE 0 1
SLACKOFF 3
MOVE 0 1 3
SWAP 1 2 3
TOGGLETRIGGERREPLACE 3 2
SLACKOFF 2
SLACKOFF 3

TOGGLETRIGGERREPLACE 0 MOVE MOVE 1 1
TRIGGER SLACKOFF: SWAP
TRIGGER SWAP: TOGGLETRIGGERREPLACE 1 TOGGLETRIGGERREPLACE SLACKOFF
SLACKOFF

4 4
2 1
1 2
0 3
1 3
SLACKOFF 0
SLACKOFF 1
SLACKOFF 2
SLACKOFF 3

SLACKOFF
TRIGGER SLACKOFF: SLACKOFF
TRIGGER SLACKOFF: SLACKOFF
TRIGGER TRIGGER: SLACKOFF

Hint

Sample Explanation 1

The order of selecting robots is $1,1,0,1,3$. The second and sixth “commands” executed are executed after triggering TRIGGER commands.

Note that the triggering time of a TRIGGER command is after the previous “command” is executed. Therefore, after the first “swap”, since robot $1$’s “right hand” points to robot $0$, which has TRIGGER SWAP: SWAP, this TRIGGER command can be triggered.

Sample Explanation 2

The order of selecting robots is $0,3,0,1,3$. The fifth and sixth “commands” executed are executed after triggering TRIGGER commands.

The first “execution” will change robot $1$’s “command” into SWAP, and robot $0$’s “command” into MOVE 1 1.

The fifth “execution” will change robot $2$’s “command” from SLACKOFF to

TRIGGER TOGGLETRIGGERREPLACE: SLACKOFF

and robot $3$’s “command” from

TRIGGER SWAP: TOGGLETRIGGERREPLACE 1 TOGGLETRIGGERREPLACE SLACKOFF

to SLACKOFF rather than TRIGGER SWAP: SLACKOFF.

Sample Explanation 3

The order of selecting robots is $0$. The second, third, and fourth “commands” executed are executed after triggering TRIGGER commands.

Note that after robot $3$ finishes “executing” its “command”, it will not then trigger its own TRIGGER “command”, even if its “right hand” points to itself.

Also, selecting a robot that has a TRIGGER command will not produce any output, so doing so is meaningless.

Sample Explanation 4

See 4.in under the problem directory. This sample does not provide sample output.

Sample Explanation 5

See 5.in under the problem directory. This sample does not provide sample output.

Notes

We will provide an executable file checker to help you check whether your output is correct. Use it by running the following command in the directory where the file is located:

./checker <input file path> <your output file path>

If your output is correct, the program will output Accepted.; otherwise, it will indicate the earliest position where the “execution” result does not match the input file.

Note that if the input file you use is not a sample input, this program will not check whether there exists a set of initial “commands” such that there is a way to select robots to obtain the corresponding “execution” result.

Source and Acknowledgements

From the THUPC2024 (Tsinghua University Student Programming Contest and Invitational Contest) finals. Thanks to THUSAA for providing the problem.

For the testdata, statement, reference solution, editorial, etc., please refer to the official THUPC repository https://thusaac.com/public.

Translated by ChatGPT 5