P13103 [GCJ 2019 Qualification] You Can Go Your Own Way

你刚刚进入了世界上最简单的迷宫。你从一个 $N \times N$ 的单位方格的西北角单元格出发，目标是到达东南角单元格。你只能进行两种类型的移动：向东移动一格，或向南移动一格。你可以进入任意单元格，但不能移动出格子外。 你本以为自己是第一个解开这个迷宫的人，但你发现了脚印。你的对手 Labyrinth Lydia 已经按照上述规则走完了迷宫！ 作为一个有创意的人，你不想重复 Lydia 的任何一步。具体来说，如果她的路径包含了从某个单元格 A 移动到相邻单元格 B 的一步，你的路径中不能包含从 A 到 B 的移动（但你可以访问 A 或 B，只要不是从 A 到 B）。请你找出一条满足条件的路径。 下图中，Lydia 的路径用蓝色表示，你的一种可行路径用橙色表示： 

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试数据，每组包含两行。第一行包含一个整数 $N$，表示迷宫的尺寸。第二行包含一个长度为 $2N-2$ 的字符串 $P$，每个字符为大写字母 E（表示向东）或 S（表示向南），表示 Lydia 的一条合法路径。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是一个长度为 $2N-2$ 的字符串，每个字符为大写字母 E 或 S，表示你的一条合法路径，且不与 Lydia 的路径冲突。保证至少存在一个解。

**样例解释** 样例 1 中，迷宫太小，你只剩下唯一一种合法解法。 样例 2 对应上图。注意，路径可以交叉。 **数据范围** - $1 \leq T \leq 100$。 - $P$ 恰好包含 $N-1$ 个 E 和 $N-1$ 个 S。 **测试点 1（5 分，可见）** - $2 \leq N \leq 10$。 **测试点 2（9 分，可见）** - $2 \leq N \leq 1000$。 **测试点 3（10 分，隐藏）** - 最多 10 个用例满足 $2 \leq N \leq 50000$。 - 其余用例满足 $2 \leq N \leq 10000$。 由 ChatGPT 4.1 翻译