题目描述

Snuke 和 Sothe 正在玩一个叫做 Connecting Game 的游戏。

游戏在一个 $n\times m$ 的矩形网格上进行，每个格子属于且仅属于一个区域。题目用字符矩阵描述这些区域：字符相同的格子属于同一个区域，并保证每个区域都是 四连通 的，即同一区域内任意两个格子都能只经过上下左右相邻的该区域格子互相到达。

最终，每个区域都会被整体染成红色或蓝色；同一个区域中的所有格子颜色必须相同。你只需要知道：对于所有区域，每一种红蓝染色组合都有可能出现。

染色完成后，按如下规则判断胜负：

• 如果存在一条只经过蓝色格子、从网格第一行连接到最后一行的路径，则 Snuke 获胜；
• 如果存在一条只经过红色格子、从网格第一列连接到最后一列的路径，则 Sothe 获胜。

路径中相邻两个格子必须共享一条边，即只能上下左右移动。

两名玩家不可能同时获胜，但有时可能出现无人获胜的染色方案。

如果对于任意一种区域染色方案，都一定至少有一名玩家获胜，则称这个网格是 valid；如果存在一种染色方案使两名玩家都无法获胜，则称这个网格是 invalid。

请判断给定网格是 valid 还是 invalid。

输入格式

第一行输入两个整数 $n,m$，表示网格的行数和列数。

接下来 $n$ 行，每行输入一个长度为 $m$ 的字符串，描述网格中的区域划分。

相同字符表示属于同一个区域。字符只可能是数字、大写英文字母或小写英文字母，并保证每个区域都是四连通的。

输出格式

如果网格一定会产生胜者，输出：

valid

否则输出：

invalid

数据范围

• $1\le n,m\le 30$；
• 所有输入字符均属于 0-9、A-Z 或 a-z；
• 每一种字符对应的区域均为四连通区域。

样例 1

输入

2 3
AAB
CCD

输出

invalid

说明

可以将区域 A、D 染成红色，将区域 B、C 染成蓝色。此时不存在蓝色的上下连通路径，也不存在红色的左右连通路径，因此该网格为 invalid。

样例 2

输入

2 2
AA
BB

输出

valid

样例 3

输入

3 3
iii
iwi
iii

输出

valid

样例 4

输入

3 7
SSnukee
SKnuthe
SSSothe

输出

invalid

来源

TopCoder SRM 637 Division I Hard，原题编号 PM 13503。