CF906E Reverses

飓风袭击了 Berland 以及郊区 Stringsvill。你打算前往那里，检查你最喜欢的字符串是否安然无恙。飓风损坏了字符串，将其某些不相交的子串进行了翻转。你拥有这根字符串在飓风发生前的照片，希望通过最少次数的子串翻转，将其还原为原始状态，并找出应该翻转哪些子串。 现在给定字符串 $s$（原始字符串）和字符串 $t$（飓风后的字符串）。你需要选择 $k$ 个 $t$ 的不相交子串，使得将这些子串翻转后，$t$ 变为 $s$，并且 $k$ 最小。

输入的第一行为字符串 $s$，第二行为字符串 $t$。两字符串长度相同，仅包含小写英文字母。$1 \leq |s| = |t| \leq 5 \cdot 10^{5}$。

第一行输出整数 $k$，表示你应翻转的最小子串数。接下来 $k$ 行，每行输出两个整数 $l_i$，$r_i$，表示需要翻转的子串区间（从第 $l_i$ 个到第 $r_i$ 个字符，字符串下标从 1 开始）。这些子串不能相交。如果有多种方案，可输出任意一种。如果无法通过翻转操作还原字符串，输出 $-1$。

由 ChatGPT 5 翻译