2815 「eJOI2018」AB 串

题目译自 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$ 在这次交换中的前缀长度。

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

在这个样例中，首先把第一个串 $1$ 个长度的前缀与第二个串 $0$ 个长度的前缀交换，即将 b 插入第二个串开头。这时两个串变成了 ab 和 bbb。接下来把第一个串 $1$ 个长度的前缀与第二个串 $3$ 个长度的前缀交换，即交换 a 和 bbb，此时两个串变成了 bbbb 和 a ，达成目标。

直接就达成了目标。

计分策略

设 $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。

数据限制