[JSOI2016]扭动的回文串

题目描述

JYY有两个长度均为 $N$ 的字符串 $A$ 和 $B$。 一个扭动字符串$S(i,j,k)$ 由 $A$ 中的第 $i$ 个字符到第 $j$ 个字符组成的子串与 $B$ 中的第 $j$ 个字符到第 $k$ 个字符组成的子串拼接而成。 比如,若 $A=$ ’XYZ’,$B=$’UVW’,则扭动字符串 $S(1,2,3)=$ ’XYVW’。 JYY 定义一个扭动的回文串为如下情况中的一个: 1. $A$ 中的一个回文串; 2. $B$ 中的一个回文串; 3. 或者某一个回文的扭动字符串$S(i,j,k)$ 现在 JYY 希望找出最长的扭动回文串。

输入输出格式

输入格式


第一行包含一个正整数 $N$。 第二行包含一个长度为 $N$ 的由大写字母组成的字符串 $A$。 第三行包含一个长度为 $N$ 的由大写字母组成的字符串 $B$。

输出格式


输出的第一行一个整数,表示最长的扭动回文串。

输入输出样例

输入样例 #1

5
ABCDE
BAECB

输出样例 #1

5

说明

**样例解释** 最佳方案中的扭动回文串如下所示(不在回文串中的字符用 . 表示): ```pain .BC.. ..ECB ``` 对于所有的数据,$1 \leq n \leq 10 ^ 5$