题目描述

原件：tmp1.png

对于某两个字符串$A$ 和 $B$，设$A$的长度为 $p$，$B$ 的长度为 $q$，若用以下形式表示他们。

我们说$A$包含 $B$，或者说 $B$是$A$的子序列，当且仅当存在

满足

你的任务是:给定三个字符串$X$、$Y$、$Z$，求 $X$和$Y$ 的一个公共子序列$W$，使得$W$包含 $Z$。

要求找出最长的这种序列$W$的长度。

输入格式

输入共三行，每行为长度不超过$500$的，小写字母组成的非空字符串

按顺序分别表示$x,y,z$

输出格式

如存在满足条件的$N$，输出$W$的长度，否则输出 NO SOLUTION

样例

helloworld
hellxebore
xr

5

样例解释

$W=\text{hxeor}$

数据范围与约定

设$L$为字符串长度，

则对于$100\%$的数据：$L\le 500$.

提示

本题要求找出的$W$首先是$X$与$Y$的公共子序列并且包含$Z$，然后才是满足这些条件的字符串里面找最长的。