Cho ma trận có kích thước \(m\) x \(n\) trong đó mỗi ô của ma trận chỉ tồn tại một trong ba giá trị:

\(0\) tương ứng là một ô trống, \(1\) tương ứng là một quả táo tươi, \(2\) tương ứng là một quả táo thối. Cứ mỗi giờ, bất kỳ quả táo tươi nào nằm cạnh một quả táo thối (theo 4 hướng trên, dưới, trái phải) thì đều bị thối. Trả về số phút tối thiểu phải trôi qua cho đến khi không còn quả táo tươi nào.

Đầu vào

Dòng đầu tiên chứa 2 số nguyên \(m, n\) \((1 \le n, m \le 100)\).

Dòng thứ hai là ma trận \(m\) x \(n\) chỉ chứa các số \(0\), \(1\) và \(2\)

Đầu ra

Số phút tối thiểu phải trôi qua cho đến khi không còn quả táo tươi nào. Nếu điều này là không thể, hãy in ra -1. Nếu ban đầu không có quả táo tươi nào thì tức là trôi qua 0 phút và bạn sẽ in ra 0.

Ví dụ 1

Đầu vào:

3 3
2 1 1
1 1 0
0 1 1

Đầu ra:

240

Ví dụ 2

Đầu vào:

3 3
2 1 1
1 1 0
1 0 1

Đầu ra:

-1

Ví dụ 3

Đầu vào:

3 3
2 0 2
2 2 0
2 2 0

Đầu ra:

0