题目描述

给定 $V$ 个点，$E$ 条边的无向图。

一开始每个点上有 T 牛，J 牛，或者没有（E）。

J 牛可以 MOVE 到一个相邻的点，

也可以 ATTACK 相邻点上的一个 T 牛。

不过操作有限制，只能按照 MOVE,ATTACK 或者 MOVE 然后 ATTACK 三种方式操作。

一个 T 牛仅能被 ATTACK 一次，被 ATTACK 后它会留在原地。 需要保证任意时刻，每个点上有且仅有一头牛。

求所有 T 牛被 ATTACK 的最大次数，并给出一个可行的操作方案。

输入格式

第一行两个整数 $V,E$，表示无向图的点数和边数。 接下来一行 $V$ 个字符，第 $i$ 个字符表示第 $i$ 个点的初始状态。 接下来 $E$ 行每行两个整数 $u,v$，表示存在一条连接 $u,v$ 的无向边。

输出格式

第一行一个整数，表示所有 T 牛被 ATTACK 的最大次数。 接下来若干行，每行以 MOVE u v 或 ATTACK u v 的形式给出，表示你的操作方案。

输入输出样例 #1

输入 #1

5 4 
TEJTJ 
1 2 
2 3 
3 4 
4 5

输出 #1

2 
MOVE 3 2 
ATTACK 2 1 
ATTACK 5 4

说明/提示

对于测试点 $1\sim5$，$1\leq V\leq 30,1\leq E\leq 50$。 对于测试点 $6\sim 10$，$1\leq V\leq 500,1\leq E\leq 2\times 10^3$。 对于测试点 $11\sim 15$，$1\leq V\leq 10^3,1\leq E\leq 5\times 10^3$。 注意：一个操作需要描述现在的位置，例如：点 $3$ 上的牛先 MOVE 到点 $2$，再 ATTACK 点 $4$，应该写为：

``` MOVE 3 2 ATTACK 2 4 ```