Longest Power-up Path in a Grid

You are given a grid of characters with P representing a power-up, X representing an obstacle, and . representing an empty cell. Your task is to determine the length of the longest contiguous path consisting solely of power-ups. You can move up, down, left, or right from one cell to another, but diagonal moves are not allowed. Each cell in the path must be unique (i.e. you cannot revisit a cell during a single path).

Note: If there are no power-ups in the grid, the longest path is considered to be 0.

Constraints: The grid dimensions and contents will be such that a brute-force DFS solution will run within the given time constraints.

Example 1:

Input:
4 4
PXP.
PXPX
PPPP
.XXP
Output:
7

</p>

Example 2:

Input:
3 5
P.P.P
XXXXX
P.P.P
Output:
1

</p>

inputFormat

The first line of input contains two integers n and m separated by a space, indicating the number of rows and columns of the grid, respectively. The following n lines each contain a string of length m representing the grid.

For example:

4 4
PXP.
PXPX
PPPP
.XXP

outputFormat

Output a single integer representing the length of the longest contiguous path that can be formed by moving horizontally or vertically through cells containing the character P.

This value should be printed to standard output.

## sample

4 4
PXP.
PXPX
PPPP
.XXP

7