codeforces#P1829E. The Lakes

    ID: 33809 远端评测题 3000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>dfs and similardsugraphsimplementation

The Lakes

Description

You are given an $n \times m$ grid $a$ of non-negative integers. The value $a_{i,j}$ represents the depth of water at the $i$-th row and $j$-th column.

A lake is a set of cells such that:

  • each cell in the set has $a_{i,j} > 0$, and
  • there exists a path between any pair of cells in the lake by going up, down, left, or right a number of times and without stepping on a cell with $a_{i,j} = 0$.

The volume of a lake is the sum of depths of all the cells in the lake.

Find the largest volume of a lake in the grid.

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains two integers $n, m$ ($1 \leq n, m \leq 1000$) — the number of rows and columns of the grid, respectively.

Then $n$ lines follow each with $m$ integers $a_{i,j}$ ($0 \leq a_{i,j} \leq 1000$) — the depth of the water at each cell.

It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $10^6$.

For each test case, output a single integer — the largest volume of a lake in the grid.

Input

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains two integers $n, m$ ($1 \leq n, m \leq 1000$) — the number of rows and columns of the grid, respectively.

Then $n$ lines follow each with $m$ integers $a_{i,j}$ ($0 \leq a_{i,j} \leq 1000$) — the depth of the water at each cell.

It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $10^6$.

Output

For each test case, output a single integer — the largest volume of a lake in the grid.

5
3 3
1 2 0
3 4 0
0 0 5
1 1
0
3 3
0 1 1
1 0 1
1 1 1
5 5
1 1 1 1 1
1 0 0 0 1
1 0 5 0 1
1 0 0 0 1
1 1 1 1 1
5 5
1 1 1 1 1
1 0 0 0 1
1 1 4 0 1
1 0 0 0 1
1 1 1 1 1
10
0
7
16
21