You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

题目译自 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

提示

样例 $1$ 解释：

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

样例 $2$ 解释：

已经是最终要求的状态了。

计分策略

设 $n$ 为你给出的操作数量，$m$ 为标准答案，本题使用 SPJ。

• 如果所有任务中 $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。

数据限制