本题是一道提交答案题，由于输入文件较大，请及早下载数据。

一切要从远古时期说起……

那时还没有跳蚤国，世界一片混乱。一位伟大的跳蚤先知，在一次意外的偶遇中，获得了一种神秘的力量。他使用这种强大的力量，统一了那片大地，建立了最初的跳蚤国。

三十年后，他离开了这片大地，前往更广阔的世界，去寻找这种力量的根源。离开跳蚤国前，他留下了一段话，并把绝大多数力量封印在了魔法阵中：“这种神奇的力量是属于 OI 的力量，想要掌握这种力量，必须要按照仪式才能解开封印。”

千年后的跳蚤国。又是一场战争，跳蚤国受到了来自蛐蛐国、跳晚国等的围攻，敌方的势力过于强大，很难阻挡。

跳蚤国王想起了先知离开前说过的话，决定用仪式解开尘封了千年的 OI 的力量，挽救跳蚤国于危亡之中。

跳蚤国王打开了魔法阵，发现这个魔法阵是九个魔法阵的叠加，他决定一个个破解魔法阵。

按照远古的仪式，跳蚤国王需要按照魔法阵的形状，将 $n$ 只跳蚤排成一个阵法的形状。这个阵法可以抽象成一个有向图。每个跳蚤可以从一些跳蚤那里接收力量，也可以把力量传递给另外一些跳蚤。有 $m$ 个这样的魔法通道，可以把一个跳蚤身上的力量单向传输到另外一个跳蚤身上。

这种属于 OI 的力量太过强大，所以没有人能掌控的时候，这种属于 OI 的力量是不稳定的。如果出现了一只跳蚤的力量经过某些魔法通道传递到了他本身，那么这个魔法阵就会因为不稳定而自爆，所以这个魔法阵是不存在环的。

每个跳蚤的身上有一个字符，而一条路径对应的就是一个字符串。先知的预言里曾经说过，只有回文串才能提供魔力，打开这个阵法；而回文串越长，自然激发出来的力量就越强。

为了最大程度的解开封印的力量，跳蚤国王希望从魔法阵中选出一些跳蚤组成一条路径，使该路径对应的字符串是最长的回文串。

因为某些魔法阵力量的残缺，有的魔法阵还规定了路径的起点或终点。

输入格式

本题为提交答案题。

所有输入数据 $\texttt{road1.in}$ ~ $\texttt{road9.in}$ 见数据下载。

对于每组数据，输入文件格式如下：

第一行两个数 $n$,$m$，表示这个图的点数和边数。

下一行两个参数 $S,T$。$S$ 表示你要找的回文路径的起点，$T$ 表示你要找的回文路径的终点。当 $S=0$ 表示起点可以为任意节点；同样，当 $T=0$ 表示终点可以为任意点。

接下来 $n$ 行每行一个字符，给出每个点上的字符。

接下来 $m$ 行，每行两个数 $u,v$，表示一条有向边 $u \rightarrow v$（$1 \leq u,v \leq n$）

输出格式

针对给定的输入数据 $\texttt{road1.in}$ ~ $\texttt{road9.in}$ 你需要分别给出输出 $\texttt{road1.out}$ ~ $\texttt{road9.out}$。

对于每组数据，给出一个数作为答案，即最长的回文路径长度。

样例输入

3 3
1 3
a
b
a
1 2
1 3
2 3

样例输出

3

样例解释

最长路径为 $1 \rightarrow 2 \rightarrow 3$，对应字符串为 "aba"，是一个回文串，长度为 $3$。

评分方式

答案为一个整数，如果正确则该测试点满分。

如何检验你的输出

我们将给出每个答案的检验值 $\mathrm{ans}$，你可以使用该值对你的结果进行校验。

对于一个测试点，设你的答案为 $x$。如果 $ ( ( x + 23333 ) \bmod 25 + 9999 ) \bmod 7$ 的值与 $\mathrm{ans}$ 相等，则你的答案可能是正确的，否则你的答案一定是错误的。

最终测试时，你的答案与标准答案完全一致才能得分。

比赛时，一个测试点只要提交了非空的文件，则算该测试点满分。

测试点分值与评分参数

数据下载

百度盘下载链接: https://pan.baidu.com/s/1dEZ4ryp 密码: tupm

对于每个输入文件，我们提供了 windows 换行符结尾和 linux 换行符结尾两种格式。

由于 5 号点和 9 号点大小特别大，我们提供了两种下载方式：你可以选择直接下载压缩包慢慢等，也可以在文件夹中选择测试点一个个下载到本地。

注意，由于本题输入文件较大，请选择方便查看大文件的文本编辑器观察数据特点。linux 下推荐 vim 或 Emacs 等，windows 下推荐 notepad++。或者另一个选择是使用一些 IDE 比如 GUIDE 打开。