Cow Tipping Attack

Farmer John is fed up with Farmer Tom and wants to tip as many of Tom’s cows as possible in a single salvo. The pastures are numbered 1..V and are connected by E bidirectional cowpaths. Each pasture initially either holds a single cow from Farmer John (denoted by J), a single cow from Farmer Tom (T), or is empty (E).

During the first salvo, each of Farmer John's cows may optionally traverse one cowpath from its current pasture (provided the destination pasture is empty) and then, from its final position, launch an attack along one cowpath to a neighboring pasture. A cow that does not move may also attack from its starting location. An attack can be performed only on a pasture that contains one of Farmer Tom’s cows, and each cow (or empty pasture used for repositioning) cannot be used more than once. No two cows may move to the same pasture, and once a cow is tipped it cannot be tipped again.

Your task is to determine the maximum number of Farmer Tom’s cows that can be tipped in the first salvo and to output a valid sequence of commands for Farmer John’s cows achieving this optimal result. A command is one of the following:

• ATTACK X Y — the cow in pasture X attacks the adjacent pasture Y (which must contain a Tom cow).
• MOVE X Y — the cow in pasture X moves to an adjacent empty pasture Y; in this case, later the cow at pasture Y will attack an adjacent pasture containing a Tom cow.

For example, consider 5 pastures arranged in a line with connections between consecutive pastures. Suppose the initial configuration is:

1: T
2: E
3: J
4: T
5: J

One optimal solution is to move the cow from pasture 3 to pasture 2 and then issue the following commands:

MOVE 3 2
ATTACK 2 1
ATTACK 5 4

This tips 2 of Farmer Tom's cows. Any valid sequence of commands that tips the maximum number may be output.

Input Format: The first line contains two integers V and E. The second line contains V tokens, where the i-th token is either J, T, or E corresponding to pasture i. Each of the next E lines contains two integers, representing a bidirectional cowpath connecting two distinct pastures.

Output Format: The first line of output should be the maximum number of Tom's cows that can be tipped. Each subsequent line should contain a command – either a move command or an attack command – describing the actions taken. If a cow moves then attacks, output two lines: one for the move and one for the subsequent attack.

inputFormat

The input begins with a line containing two integers V (1 ≤ V ≤ 1000) and E (1 ≤ E ≤ 5000). The next line contains V tokens: each token is either J, T, or E indicating the content of pastures 1 through V. Each of the following E lines contains two integers u and v (1 ≤ u, v ≤ V, u ≠ v) that denote a bidirectional cowpath connecting pastures u and v. No pair of pastures is connected by more than one cowpath.

outputFormat

On the first line, output a single integer representing the maximum number of Tom's cows that can be tipped in the first salvo. Following that, output a sequence of commands – one command per line – that causes the maximum number of tips to occur. Valid commands are of those forms:

• ATTACK X Y: the cow in pasture X attacks pasture Y.
• MOVE X Y: the cow in pasture X moves to pasture Y (which is empty), from where it will later attack a neighboring pasture.

If a cow moves and then attacks, output two commands: first the MOVE command, then the ATTACK command. Any valid sequence that achieves the maximum tip count is accepted.

sample

5 4
T E J T J
1 2
2 3
3 4
4 5

2
MOVE 3 2
ATTACK 2 1
ATTACK 5 4

</p>