AT_arc172_f [ARC172F] Walking

### 问题描述 在 AtCoder 王国中有 $2\times N$ 个交叉口，每个交叉口编号从 $1$ 到 $2\times N$。此外，在 AtCoder 王国中有以下 $3$ 种单向道路： - 类型 A: 对于 $2 \leq i \leq N$，从交叉口 $2i-3$ 到交叉口 $2i-1$ 的道路 - 类型 B: 对于 $2 \leq i \leq N$，从交叉口 $2i-2$ 到交叉口 $2i$ 的道路 - 类型 C: 对于 $1 \leq i \leq N$，连接交叉口 $2i-1$ 和交叉口 $2i$ 的方向为 $s_i$ 的道路 这里，$s_i$ 是 `X` 或 `Y`，其中 `X` 表示从交叉口 $2i-1$ 到交叉口 $2i$ 的方向，而 `Y` 表示从交叉口 $2i$ 到交叉口 $2i-1$ 的方向。 高桥君希望通过进行步行几次，对于每个 $1 \leq i \leq N$，使连接交叉口 $2i-1$ 和交叉口 $2i$ 的类型 C 道路的方向为 $t_i$。 步行操作 从任意交叉口出发，重复以下操作 $0$ 次或多次： - 如果可以走上类型 C 的道路，则沿着该道路走到下一个交叉口。 - 如果无法走上类型 C 的道路，但可以走上类型 A 或 B 的道路，则沿着该道路走到下一个交叉口。 然后，将经过的所有类型 C 的道路的方向反转。 请计算达到目的所需的最少步行次数，并给出达到目的的最少步行次数的方法。在此问题的约束条件下，可以证明可以有限次步行达到目的地。

以以下形式输入数据： > $ N $ > > $ s_1\ s_2\ \cdots\ s_N $ > > $ t_1\ t_2\ \cdots\ t_N $

请以以下形式输出。假设步行次数为 $X$。此外，第 $i$ 次步行（$1 \leq i \leq X$）从交叉口 $a_i$ 出发，最终在交叉口 $b_i$ 终止。 > $X$ > > $a_1$ $b_1$ > > $a_2$ $b_2$ > > $ \vdots $ > > $a_X$ $b_X$

- $N$ 是满足 $1 \leq N \leq 4000$ 的整数 - $s_1, s_2, \dots, s_N$ 是 `X` 或 `Y` - $t_1, t_2, \dots, t_N$ 是 `X` 或 `Y` 【样例解释 1】 在这个样例中，高桥君将按照以下步骤行走： - 从交叉口 2 出发。 - 由于从交叉口 2 没有类型 C 道路可供前进，沿着类型 B 道路走到交叉口 4。 - 由于从交叉口 4 有类型 C 道路可供前进，沿着类型 C 道路走到交叉口 3。 - 由于从交叉口 3 没有类型 C 道路可供前进，沿着类型 A 道路走到交叉口5。 - 由于从交叉口 5 有类型 C 道路可供前进，沿着类型 C 道路走到交叉口 6。 - 由于从交叉口 6 没有类型 C 道路可供前进，沿着类型 B 道路走到交叉口 8。 - 由于从交叉口 8 有类型 C 道路可供前进，沿着类型 C 道路走到交叉口 7。 - 在交叉口 7 结束。 这次步行经过了以下三条类型 C 道路： - 连接交叉口 3 和交叉口 4 的道路。 - 连接交叉口 5 和交叉口 6 的道路。 - 连接交叉口 7 和交叉口 8 的道路。 这些道路的方向被反转，因此连接交叉口 $2i−1$ 和交叉口 $2i$（其中 $i=1,2,3,4,5$）的道路的方向现在分别为 `X`、`X`、`Y`、`X`、`X`，到达了目的地。