Inna and Dima

## 题目描述 Inna和Dima在商店买了一张 n * m 的桌子，桌子的每一个单元格上都有一个字符，字符集为("D","I","M","A")。 Inna实在是太爱Dima了，所以她想在桌子上找出一条最长的路线，使得这条路线中包含尽可能多的Dima的名字（有序，即必须是连续的DIMA）。 Inna的路线选取方式会遵循以下原则： 1.一开始，Inna会在桌子上找到所有的"D"，把他们作为起点。 2.Inna会在当前格子的周围四个相邻的格子中选取一个格子，她会从"D"走到"I"，从"I"走到"M"，从"M"走到"A"。这样，她就认为自己走完了一次Dima的名字。 3.Inna每走完一个格子，就会在该格子四周相邻的四个格子中选一个走，即上下左右四个方向，（当然，她不能走出这张桌子）。Inna从不跳过一个字母。因此，从字母"D"开始，她总是走到字母"I"，从字母"I"开始，她总是走到字母"M"，从字母"M"开始，她总是走到字母"A"，从字母"A"开始，她总是走到字母"D"。 因为桌子的不同，Inna能走的Dima的名字的次数也不同，有时她可以走有限次，有时她可以走无限次，有时她甚至不能走完一次Dima的名字。 现在，她想知道她能否至少走完一次Dima的名字。若可以，她最多能走多少次或者她能否走无限次？ ## 输入输出格式： ### 输入格式： 第一行两个正整数n和m，表示这张桌子有n行m列。 接下来n行，每行m个字符，字符集为("D","I","M","A")。 输入数据保证至少有一个字符为"D"。 ### 输出格式： 如果Inna连一次Dima的名字都不能走，则输出"Poor Dima!"（不包含引号）。 如果Inna可以走无限次Dima的名字，则输出"Poor Inna!"（不包含引号）。 如果Inna可以走有限次Dima的名字，输出她能走的最大次数。 参见样例。 ## 说明： 在第一个样例中，Inna一次Dima的名字都不能走。 在第二个样例中，Inna可以走无限次Dima的名字。 在第三个样例中，Inna最多走4次Dima的名字，从(1, 1)出发。

Inna and Dima bought a table of size $ n×m $ in the shop. Each cell of the table contains a single letter: "D", "I", "M", "A". Inna loves Dima, so she wants to go through his name as many times as possible as she moves through the table. For that, Inna acts as follows: 1. initially, Inna chooses some cell of the table where letter "D" is written; 2. then Inna can move to some side-adjacent table cell that contains letter "I"; then from this cell she can go to one of the side-adjacent table cells that contains the written letter "M"; then she can go to a side-adjacent cell that contains letter "A". Then Inna assumes that she has gone through her sweetheart's name; 3. Inna's next move can be going to one of the side-adjacent table cells that contains letter "D" and then walk on through name DIMA in the similar manner. Inna never skips a letter. So, from the letter "D" she always goes to the letter "I", from the letter "I" she always goes the to letter "M", from the letter "M" she always goes to the letter "A", and from the letter "A" she always goes to the letter "D". Depending on the choice of the initial table cell, Inna can go through name DIMA either an infinite number of times or some positive finite number of times or she can't go through his name once. Help Inna find out what maximum number of times she can go through name DIMA.

The first line of the input contains two integers $ n $ and $ m $ $ (1<=n,m<=10^{3}) $ . Then follow $ n $ lines that describe Inna and Dima's table. Each line contains $ m $ characters. Each character is one of the following four characters: "D", "I", "M", "A". Note that it is not guaranteed that the table contains at least one letter "D".

If Inna cannot go through name DIMA once, print on a single line "Poor Dima!" without the quotes. If there is the infinite number of names DIMA Inna can go through, print "Poor Inna!" without the quotes. Otherwise print a single integer — the maximum number of times Inna can go through name DIMA.

1 2
DI

Poor Dima!

2 2
MA
ID

Poor Inna!

5 5
DIMAD
DIMAI
DIMAM
DDMAA
AAMID

4

Notes to the samples: In the first test sample, Inna cannot go through name DIMA a single time. In the second test sample, Inna can go through the infinite number of words DIMA. For that, she should move in the clockwise direction starting from the lower right corner. In the third test sample the best strategy is to start from the cell in the upper left corner of the table. Starting from this cell, Inna can go through name DIMA four times.