Взлом

시간 제한2초메모리 제한1024 MB

요약

n×m 격자에서 인접한 칸으로 이동하며 값이 1씩 커지는 순차 정수 경로 중 가장 긴 길이를 구한다.

난이도: 보통10점 중 6점
유형: 그래프, DFS, 동적 계획법
정답자: 아직 제출이 없습니다

문제

I AM SHERLOCKED

Защитный код на телефоне Ирэн Адлер

После заполучения заблокированного телефона Ирэн Адлер, содержащего неизвестные, но невероятно важные сведения, перед Шерлоком встала непростая задача его взлома. При всевозможных исследованиях телефона, им было выяснено, что после первой же неудачной попытки ввода пароля всё содержимое аппарата безвозвратно уничтожается микровзрывом.

Экран разблокировки представляет собой таблицу $n \times m$ целых чисел. После долгих раздумий над оставленными Ирэн намёками, Шерлок понял, как ему разблокировать телефон. Для этого, ему необходимо найти в этой таблице цепочку последовательных натуральных чисел максимальной длины. Цепочкой называется последовательность клеток таблицы, в которой каждые две последовательные клетки являются соседними в таблице.

Помогите Шерлоку найти длину такой цепочки.

입력

В первой строке заданы числа $n$ и $m$ ( $1 \le n, m \le 1000$ ). Далее, в $n$ строках задано по $m$ чисел $a\_{i,j}$ --- элементы таблицы ( $1 \le a\_{i,j} \le 10 \times n \times m$ ).

출력

Выведите единственное число --- максимальную длину цепочки последовательных чисел в таблице.

예제2

예제 1
입력
```
3 3
1 2 3
6 5 4
7 8 9
```
예상 출력
```
9
```
예제 2
입력
```
3 3
1 1 1
1 2 1
1 1 1
```
예상 출력
```
2
```