SP25477 TAP2015G - Generating alien DNA II

由于 SPOJ 的限制，这道题目已经在原版的基础上进行了修改，以允许一个输入文件中包含多个测试用例。2015 年阿根廷编程竞赛的原版题目（西班牙语）可以通过以下链接查看: 。 从微小的微生物到巨大的鲸鱼、恐龙及人类，地球上的所有生命都有一个共同的特征，那就是 DNA。DNA 是目前已知的唯一一种遗传信息传递和复制的机制，这也引发了现代生物学中一个重要的问题：DNA 是否是编码遗传信息的唯一方式，还是有其他潜在的可能性？ 古尔德教授是一名专注于外星生命研究的理论生物学家，他考虑的研究问题是是否存在不以 DNA 形式存储遗传信息的外星生命。目前，他开发了一个模型，其中遗传信息以伪核苷酸链的形式存在，我们用字符 **'b', 'd', 'o', 'p', 'q', 'v', 'w'** 和 **'x'** 表示这些伪核苷酸。每种伪核苷酸都有一个对应的共轭物：**'o', 'v', 'w'** 和 **'x'** 自身即为自己的共轭物，**'b'** 和 **'d'** 互为共轭物，**'p'** 和 **'q'** 互为共轭物。 根据古尔德教授的模型，一个生物体可以通过从其伪核苷酸链的某个位置开始进行“突变”，来改变链的第二部分。突变作用是对该位置之后的部分进行反转并将其转换为共轭。具体地说，如果原始的伪核苷酸链是 **a $ _{1} $ a $ _{2} $ ... a $ _{N} $**，而突变从位置 **i** 开始，则最终结果是 **a $ _{1} $ a $ _{2} $ ... a $ _{i-1} $ ã $ _{N} $ ã $ _{N-1} $ ... ã $ _{i+1} $ ã $ _{i} $**，其中 **ã $ _{k} $** 表示原来位于位置 **k** 的伪核苷酸的共轭物。 在演化过程中，一个生物体可能会经历多次类似的突变，唯一的限制是连续的突变必须从越来越靠近伪核苷酸链末端的位置开始。例如，链 **"bdopqvwx"** 可以先从位置 **3** 突变成为链 **"bdxwvpqo"**，然后从位置 **7** 再次突变为 **"bdxwvpop"**。但这两个突变不能以相反顺序进行。 目前，古尔德教授有两条特别值得关注的伪核苷酸链。他希望知道，第一条链最少需要经过多少次突变才能变成第二条链。你能帮他解决这个问题吗？

输入包含多个测试用例。对于每个测试用例，第一行有一个整数 **N**，表示两个伪核苷酸链的长度（$1 \le N \le 10^5$）。接下来的两行，每行包含一个由 **N** 个字符 **'b', 'd', 'o', 'p', 'q', 'v', 'w'** 和 **'x'** 组成的字符串，分别表示一条伪核苷酸链。

对于每个测试用例，输出一行，包含一个整数，表示第一条链变为第二条链所需的最少突变次数。如果无法变换，则输出 **-1**。 **本翻译由 AI 自动生成**