题目描述

给定 $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\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^5$。

注意：一个操作需要描述现在的位置，例如：点 $3$ 上的牛先 MOVE 到点 $2$，再 ATTACK 点 $4$，应该写为：

MOVE 3 2
ATTACK 2 4