Problem Description

In a grid representing a city, 0 represents humans and 1 represents zombies. Each hour, zombies infect all adjacent humans (up, down, left, right). Find the minimum number of hours needed to infect all humans. If impossible, return -1.

Input Format

First line contains m and n (grid dimensions). Next m lines contain n space-separated integers (0 or 1).

Output Format

Single integer representing hours needed to infect all humans, or -1 if impossible.

Constraints

• 1 ≤ m, n ≤ 100

• Grid contains only 0s (humans) and 1s (zombies)

• At least one cell in the grid

• Zombies spread to 4-directionally adjacent cells only

• If no humans exist initially, return 0

Sample Input/Output

3 3
1 0 0
0 0 0
0 0 1

2

Explanation

Hour 0: Zombies at (0,0) and (2,2). Hour 1: Infection spreads to adjacent humans. Hour 2: All remaining humans are infected. Total time: 2 hours.