小红拿到了一个字符矩阵，矩阵仅由'r'、'e'、'd'三种字符组成。她初始站在左上角，每次可以走到一个相邻的字符上（每个字符上、下、左、右最多4个相邻）。但有个限制，小红不能从'r'走到'd'，从'e'走到'r'，从'd'走到'e'，其他情况都能走。 小红想知道，从左上角走到右下角至少需要多少步？

输入描述:

第一行输入两个正整数和，代表矩阵的行数和列数。接下来的行，每行输入一个长度为的字符串，用来表示矩阵。

输出描述:

如果小红无法到达右下角，则输出-1。否则输出一个整数，代表小红的最少移动步数。