题目描述

今天我们来解决经典的最长公共子串问题，但这里有两个额外条件：

1. 字符串是循环的；
2. 在某些情况下，我们要在两个以上字符串之间寻找最长公共子串。

更形式化地说，给定一组循环字符串 $\{s_1,\dots,s_k\}$，每个字符串长度均为 $n$。

若存在一对下标 $1\le i,j\le |t|$，使得 $t(i,j)=p$，则称字符串 $p$ 是循环字符串 $t$ 的一个子串。在本题中，我们要找到一个最长的字符串 $p$，使得它同时是所有循环字符串 $\{s_1,\dots,s_k\}$ 的子串。

在上述定义中，$|t|$ 表示字符串 $t$ 的长度；$t(i,j)$ 表示从位置 $i$ 开始、到位置 $j$ 结束的子串。当 $i>j$ 时，允许从字符串末尾绕回开头。也就是说：

• 当 $i\le j$ 时，$t(i,j)=t_i t_{i+1}\dots t_j$；
• 当 $i>j$ 时，$t(i,j)=t_i t_{i+1}\dots t_{|t|} t_1 t_2\dots t_j$。

请编写程序 common，在给定 $k$ 个循环字符串后，求出它们的最长公共子串的长度。

注意：只有最初给定的字符串是循环的，我们要找的公共子串本身并不是循环串。

输入格式

第一行输入两个整数 $n$ 和 $k$，分别表示每个字符串的长度以及字符串个数。

接下来 $k$ 行，每行一个仅由小写拉丁字母组成的字符串。

输出格式

输出一个整数，表示最长公共子串的长度。

数据范围

• $1\le n\le 100000$
• $2\le k\le 10$

子任务

只有当某个子任务的所有测试全部通过时，才能获得该子任务的分数。

样例 #1

输入 #1

5 2
fabcq
bcdda

输出 #1

3

说明 #1

最长公共子串是 abc：

fabcq
bcdda