← 返回题目列表

Codeforces · 1012/D

D. AB 弦

中文机器翻译题面 查看原题

有两个字符串 s 和 t,仅由字母 a 和 b 组成。您可以多次进行以下操作:选择 s 前缀、t 前缀并交换它们。前缀可以为空,也可以与整个字符串一致。

你的任务是找到一系列操作,其中一个字符串仅包含 a 字母,另一个字符串仅包含 b 字母。应尽量减少操作次数。

输入

第一行包含字符串 s (1 ≤ |s| ≤ 2·105)。

第二行包含字符串 t (1 ≤ |t| ≤ 2·105)。

这里|s|和|t|分别表示 s 和 t 的长度。保证至少一个字符串包含至少一个a字母并且至少一个字符串包含至少一个b字母。

输出

第一行应包含一个整数 n (0 ≤ n ≤ 5·105) - 操作数。

接下来的 n 行中的每一行都应包含两个以空格分隔的整数 ai、bi - 分别是要交换的 s 和 t 的前缀长度。

如果有多种可能的解决方案,您可以打印其中任何一个。保证存在给定约束的解决方案。

示例

输入 #1

bab
bb

输出 #1

2
1 0
1 3

输入 #2

bbbb
aaa

输出 #2

0

注意

在第一个示例中,您可以通过两个操作来解决问题:

1. 交换第一个长度为 1 的字符串的前缀和第二个长度为 0 的字符串的前缀。交换后,您将得到字符串 ab 和 bbb。
2. 交换第一个长度为 1 的字符串的前缀和第二个长度为 3 的字符串的前缀。交换后,您将得到字符串 bbbb 和 a。

在第二个示例中,字符串已经合适,因此不需要任何操作。