AT_arc172_f [ARC172F] Walking

[problemUrl]: https://atcoder.jp/contests/arc172/tasks/arc172_f AtCoder 王国には $ 2N $ 個の交差点があり、各交差点には $ 1 $ から $ 2N $ までの番号が付けられています。 また、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 の道路の向きを反転させる。 最小何回のウォーキングで目的を達成できるかを計算し、最小回数で目的を達成する方法を $ 1 $ つ答えてください。 なお、この問題の制約下では有限回で目的を達成できることが証明できます。

入力は以下の形式で標準入力から与えられます。 > $ 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` ### Sample Explanation 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 $ でウォーキングを終える。 ここで、このウォーキングでは、以下の $ 3 $ 本のタイプ C の道路を通っています。 - 交差点 $ 3 $ と交差点 $ 4 $ を結ぶ道路 - 交差点 $ 5 $ と交差点 $ 6 $ を結ぶ道路 - 交差点 $ 7 $ と交差点 $ 8 $ を結ぶ道路 これらの道路の向きが反転するため、$ i\ =\ 1,\ 2,\ 3,\ 4,\ 5 $ について交差点 $ 2i-1 $ と交差点 $ 2i $ を結ぶ道路の向きは順に `X`、`X`、`Y`、`X`、`X` となり、目的を達成します。 ### Sample Explanation 2 最初の時点で目的が達成されているため、$ 1 $ 回もウォーキングを行う必要がないことに注意してください。