题目描述

题目译自 eJOI2018 Problem C. AB-Strings

你有两个字符串 $s,t$，它们其中仅包含字母 a 和 b。你可以多次进行如下操作：选出一个 $s$ 的前缀和一个 $t$ 的前缀并交换它们。（注意，这个前缀既可以为空也可以为整个串）

你的任务是找出一个操作序列使得进行这些操作后，一个字符串只包含字符 a，而另一个只包含字符 b。

你应该尽可能的进行最少的操作次数，但非最优解仍可能得到一部分分数，详情见「数据范围与提示」一栏。

输入格式

输入两行为两个字符串 $s,t$。

输出格式

输出第一行为一个整数 $n$（$0\leq n\leq 5\times 10^5$），表示操作总数。

接下来的 $n$ 行，每行包含两个整数 $a_i,b_i$，分别为 $s,t$ 在这次交换中的前缀长度。

如果有多种可能的方案，则可以输出任意一种。

bab
bb

2
1 0
1 3

bbbb
aaa

0

数据范围与提示

计分策略

设 $n$ 为你给出的操作数量，$m$ 为标准答案。

• 如果所有任务中 $n=m$，那么将得到 $100\%$ 的分数。

• 如果所有任务中 $n\leq m+2$，那么将得到 $70\%$ 的分数。（四舍五入到最接近的整数）

• 如果所有任务中 $n\leq 2m+2$，那么将得到 $50\%$ 的分数。（四舍五入到最接近的整数）

• 如果所有任务中 $n\leq 5\times 10^5$，那么将得到 $30\%$ 的分数。（四舍五入到最接近的整数）

• 如果至少一个任务中 $n > 5\times 10^5$，那么将得到 $0\%$ 的分数。

对于 $100\%$ 的数据，保证 $1\leq \lvert s\rvert,\lvert t\rvert \leq 2\times 10^5$，$\lvert s\rvert,\lvert t\rvert$ 分别代表 $s,t$ 的长度，且保证至少有一个串中包含至少一个字符 a，至少一个串中包含至少一个字符 b。

数据限制