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，到达了目的地。