P13961 [ICPC 2023 Nanjing R] 华丽收场

在猪之国，《Slay the Pig》是当下最流行的肉鸽游戏。在游戏中，玩家们通过使用卡牌来对抗邪恶的土豆大魔王（Evil Potato Lord）。 游戏的主要规则如下： - 游戏开始时，玩家有一个起始手牌集合和一个自顶向下排列好的抽牌堆。 - 在游戏的任意时刻，卡牌只会存在于玩家的手牌中或者抽牌堆里。 - 玩家可以使用手牌中的卡牌，使用卡牌会先让该卡牌被丢弃，然后触发该卡牌的效果。 - 玩家只有在上一张卡牌的所有效果都被触发完毕后，才可以使用下一张卡牌。 本题中，简单起见，我们只考虑抽牌这一种效果。 抽牌的规则如下： - 当使用可以抽牌的卡牌时，会按自顶向下的顺序将若干张卡牌从抽牌堆依次加入到手牌中。 - 玩家有一个手牌数量上限 $k$，任意时刻玩家的手牌数量不能超过 $k$。 - 当玩家试图抽牌时，如果玩家此时的手牌数量已经为 $k$，则不会将这张卡牌加入到手牌，而是将它直接从抽牌堆中丢弃，且不触发这张卡牌的任何效果。 - 当玩家试图抽牌时，如果此时抽牌堆为空，则什么都不会发生。 在这个游戏中，以“华丽收场”这张卡牌为核心的卡组是最为强大的。因为一旦这张牌被使用，它会对所有敌人造成大量的伤害从而轻易地赢得游戏胜利。然而华丽收场也有着苛刻的使用条件，即使用时玩家的抽牌堆必须是空。也就是说，此时所有卡牌必须已经被使用，或被丢弃，或在玩家的手牌中。 鳖皇（Bie-Bot）是猪之国中仅次于 Mysterious Oscar 的最聪明的猪，他也在使用基于华丽收场的卡组。卡组由以下四种卡牌组成： :::align{center}  ::: - 华丽收场（Grand Finale）：游戏中最强大的卡牌, 保证有且仅有一张华丽收场在鳖皇的卡组中。这张卡仅能在抽牌堆为空时被打出。 - 快斩（Quick Slash）：使用这张卡之后可以从抽牌堆抽一张牌。 - 后空翻（Backflip）：使用这张卡之后可以从抽牌堆抽两张牌。 - 伤口（Wound）：一张状态牌，一旦这张牌在玩家的手牌中，就不能被使用。 在游戏开始时，鳖皇幸运地在他的起始手牌中获得了唯一一张华丽收场，并且鳖皇提前得知了他的抽牌堆自顶向下每一张牌分别是什么。现在，他的目标是成功使用华丽收场。 鳖皇想要知道，在最优策略下，达成目标所需的最小手牌数量上限 $k$。 作为猪之国第三聪明的玩家，您能帮帮鳖皇吗？ 更正式地，给定一个长度为 $n$ 的字符串 $S_{H}$ 表示鳖皇的起始手牌，和一个长度为 $m$ 的字符串 $S_{P}$ 自顶向下地表示鳖皇的抽牌堆。 这两个字符串均由大写字母 `G`, `Q`, `B` 和 `W` 组成，分别表示起始手牌或抽牌堆对应位置的卡牌为华丽收场，快斩，后空翻和伤口。 鳖皇可以根据前文提到的规则使用这些卡牌。 请输出鳖皇最终能成功使用华丽收场所需的最小手牌数量上限 $k$（$k \geq n$），或者声明不存在这样的 $k$。

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据： 第一行输入两个整数 $n$ 和 $m$（$1 \leq n, m \leq 2500$）表示鳖皇的起始手牌数量以及抽牌堆的卡牌的数量。 第二行输入一个长度为 $n$ 的字符串 $S_{H}$ 表示鳖皇的起始手牌。字符串由大写字母 `G`，`Q`，`B`，`W` 组成。保证字符 `G` 仅在字符串 $S_{H}$ 中出现一次。 第三行输入一个长度为 $m$ 的字符串 $S_{P}$ 自顶向下地表示鳖皇抽牌堆。字符串由大写字母 `Q`，`B`，`W` 组成。 保证所有数据 $(n + m)$ 之和不超过 $5 \times 10^4$。

每组数据输出一行一个整数，表示成功使用华丽收场需要的最小手牌数量上限 $k$（$k \geq n$）。如果无法使用华丽收场，输出 $\texttt{IMPOSSIBLE}$。

以下使用“手牌/抽牌堆”字符串表示当前状况。对于第一组测试数据，一种可行的最优策略是： - BG/BQWBWW $\overset{B}{\longrightarrow}$ BQG/WBWW - BQG/WBWW $\overset{Q}{\longrightarrow}$ BWG/BWW - BWG/BWW $\overset{B}{\longrightarrow}$ BWG/W（抽牌过程中会移除一个 `W'，因为此时手牌上限已满） - BWG/W $\overset{B}{\longrightarrow}$ WWG/$\emptyset$（只会抽取一个 `W' 因为抽取第二张牌时抽牌堆为空） - WWG/$\emptyset$ $\overset{G}{\longrightarrow}$ 成功使用华丽收场！