로봇 주차

NxM 크기의 주차장 지도가 주어진다.

• C: 자동차의 위치
• P: 주차 공간의 위치
• .: 빈 칸 (이동 가능)

각 자동차는 상하좌우로 인접한 빈 칸이나 주차 공간으로 이동할 수 있다.
모든 자동차가 서로 다른 주차 공간에 도착하는 데 걸리는 최대 이동 시간의 최솟값을 구하는 프로그램을 작성하시오.
자동차의 수와 주차 공간의 수는 같다.

이동 시간은 각 자동차가 출발지에서 주차 공간까지 이동하는 최단 거리(BFS)이며,
모든 자동차가 주차를 완료하는 시간은 가장 오래 걸린 자동차의 이동 시간이다.

입력

첫째 줄에 N과 M이 공백으로 구분되어 주어진다. (2 <= N, M <= 50)
둘째 줄부터 N개의 줄에 지도가 주어진다.

출력

모든 자동차가 주차 공간에 도착하는 데 걸리는 최소 최대 시간을 출력한다.
만약 모든 자동차를 주차시키는 것이 불가능하면 -1을 출력한다.

입출력 예시

입력 1

3 4
C.P.
..P.
C..P

출력 1

3

입력 2

4 5
.C.P.
.....
.C..P
....P

출력 2

3