F - Walking Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

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 は 1 \leq N \leq 4000 を満たす整数
  • s_1, s_2, \dots, s_N は X または Y
  • t_1, t_2, \dots, t_N は X または Y

入力

入力は以下の形式で標準入力から与えられます。

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

入力例 1

5
XYXYX
XXYXX

出力例 1

1
2 7

この入力例では、高橋君は以下のようなウォーキングを行います。

  • 交差点 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 となり、目的を達成します。

入力例 2

5
XXYYX
XXYYX

出力例 2

0

最初の時点で目的が達成されているため、1 回もウォーキングを行う必要がないことに注意してください。

入力例 3

5
XXXXX
YYYYY

出力例 3

5
1 2
3 4
5 6
7 8
9 10

入力例 4

20
XXXYXYYXXXYXXXXYYXXY
XXYXYYXXYXXYXYXYXYXY

出力例 4

5
14 18
29 38
14 26
5 10
27 35

入力例 5

20
YXYXYXYYYXYYXYYXYXXX
XXXXXYXYYYXYYXXYYYXY

出力例 5

5
29 36
10 38
2 3
4 7
28 40

Score: 1000 points

Problem Statement

The Kingdom of AtCoder has 2N intersections labeled with numbers from 1 to 2N. Additionally, there are three types of one-way roads in the kingdom:

  • Type A: For each 2 \leq i \leq N, there is a road from intersection 2i-3 to intersection 2i-1.
  • Type B: For each 2 \leq i \leq N, there is a road from intersection 2i-2 to intersection 2i.
  • Type C: For each 1 \leq i \leq N, there is a road connecting intersection 2i-1 and intersection 2i with direction s_i.

Here, s_i is X or Y, where direction X means the road goes from intersection 2i-1 to intersection 2i, and direction Y means it goes from intersection 2i to intersection 2i-1.

Takahashi wants to walk several times so that for each 1 \leq i \leq N, the direction of Type-C road connecting intersections 2i-1 and 2i will be t_i.

What is a walk?

Start at any intersection and repeat the following action zero or more times:

  • If it is possible to proceed to a Type-C road from the current intersection, walk along the Type-C road to the next intersection.
  • Otherwise, if it is possible to proceed to a Type-A or B road from the current intersection, walk along that road to the next intersection.

Then, reverse the directions of all Type-C roads that were passed.

Calculate the minimum number of walks needed to achieve the goal and provide one method to achieve the goal in the minimum number of walks. Under the constraints of this problem, it can be proved that the goal can be achieved in a finite number of walks.

Constraints

  • N is an integer such that 1 \leq N \leq 4000.
  • Each of s_1, s_2, \dots, s_N is X or Y.
  • Each of t_1, t_2, \dots, t_N is X or Y.

Input

The input is given from Standard Input in the following format:

N
s_1 s_2 \cdots s_N
t_1 t_2 \cdots t_N

Output

Print your solution in the following format, where X is the number of walks, and the i-th walk (1 \leq i \leq X) starts at intersection a_i and finishes at intersection b_i.

X
a_1 b_1
a_2 b_2
\vdots
a_X b_X

Sample Input 1

5
XYXYX
XXYXX

Sample Output 1

1
2 7

In this sample input, Takahashi will walk as follows:

  • Start at intersection 2.
  • Since there is no Type-C road to proceed from intersection 2, walk along the Type-B road to intersection 4.
  • Since there is a Type-C road to proceed from intersection 4, walk along the Type-C road to intersection 3.
  • Since there is no Type-C road to proceed from intersection 3, walk along the Type-A road to intersection 5.
  • Since there is a Type-C road to proceed from intersection 5, walk along the Type-C road to intersection 6.
  • Since there is no Type-C road to proceed from intersection 6, walk along the Type-B road to intersection 8.
  • Since there is a Type-C road to proceed from intersection 8, walk along the Type-C road to intersection 7.
  • Finish at intersection 7.

This walk passes through the following three Type-C roads:

  • The road connecting intersection 3 and intersection 4.
  • The road connecting intersection 5 and intersection 6.
  • The road connecting intersection 7 and intersection 8.

The directions of these roads are reversed, so the directions of the roads connecting intersections 2i-1 and 2i for i = 1, 2, 3, 4, 5 are now X, X, Y, X, X, respectively, achieving the goal.

Sample Input 2

5
XXYYX
XXYYX

Sample Output 2

0

Note that the goal is already achieved at the beginning, so there is no need to walk even once.

Sample Input 3

5
XXXXX
YYYYY

Sample Output 3

5
1 2
3 4
5 6
7 8
9 10

Sample Input 4

20
XXXYXYYXXXYXXXXYYXXY
XXYXYYXXYXXYXYXYXYXY

Sample Output 4

5
14 18
29 38
14 26
5 10
27 35

Sample Input 5

20
YXYXYXYYYXYYXYYXYXXX
XXXXXYXYYYXYYXXYYYXY

Sample Output 5

5
29 36
10 38
2 3
4 7
28 40