{"problem":{"name":"[GDCPC 2023] Path Planning","description":{"content":"There is a grid with $n$ rows and $m$ columns. Each cell of the grid has an integer in it, where $a_{i, j}$ indicates the integer in the cell located at the $i$-th row and the $j$-th column. Each inte","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9698"},"statements":[{"statement_type":"Markdown","content":"There is a grid with $n$ rows and $m$ columns. Each cell of the grid has an integer in it, where $a_{i, j}$ indicates the integer in the cell located at the $i$-th row and the $j$-th column. Each integer from $0$ to $(n \\times m - 1)$ (both inclusive) appears exactly once in the grid.\n\nLet $(i, j)$ be the cell located at the $i$-th row and the $j$-th column. You now start from $(1, 1)$ and need to reach $(n, m)$. When you are in cell $(i, j)$, you can either move to its right cell $(i, j + 1)$ if $j < m$ or move to its bottom cell $(i + 1, j)$ if $i < n$.\n\nLet $\\mathbb{S}$ be the set consisting of integers in each cell on your path, including $a_{1, 1}$ and $a_{n, m}$. Let $\\text{mex}(\\mathbb{S})$ be the smallest non-negative integer which does not belong to $\\mathbb{S}$. Find a path to maximize $\\text{mex}(\\mathbb{S})$ and calculate this maximum possible value.\n\n## Input\n\nThere are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:\n\nThe first line contains two integers $n$ and $m$ ($1 \\le n, m \\le 10^6$, $1 \\le n \\times m \\le 10^6$) indicating the number of rows and columns of the grid.\n\nFor the following $n$ lines, the $i$-th line contains $m$ integers $a_{i, 1}, a_{i, 2}, \\cdots, a_{i, m}$ ($0 \\le a_{i, j} < n \\times m$) where $a_{i, j}$ indicates the integer in cell $(i, j)$. Each integer from $0$ to $(n \\times m - 1)$ (both inclusive) appears exactly once in the grid.\n\nIt's guaranteed that the sum of $n \\times m$ of all test cases will not exceed $10^6$.\n\n## Output\n\nFor each test case output one line containing one integer indicating the maximum possible value of $\\text{mex}(\\mathbb{S})$.\n\n[samples]\n\n## Note\n\nFor the first sample test case there are $3$ possible paths.\n\n- The first path is $(1, 1) \\to (1, 2) \\to (1, 3) \\to (2, 3)$. $\\mathbb{S} = \\{1, 2, 4, 5\\}$ so $\\text{mex}(\\mathbb{S}) = 0$.\n- The second path is $(1, 1) \\to (1, 2) \\to (2, 2) \\to (2, 3)$. $\\mathbb{S} = \\{1, 2, 0, 5\\}$ so $\\text{mex}(\\mathbb{S}) = 3$.\n- The third path is $(1, 1) \\to (2, 1) \\to (2, 2) \\to (2, 3)$. $\\mathbb{S} = \\{1, 3, 0, 5\\}$ so $\\text{mex}(\\mathbb{S}) = 2$.\n\nSo the answer is $3$.\n\nFor the second sample test case there is only $1$ possible path, which is $(1, 1) \\to (1, 2) \\to (1, 3) \\to (1, 4) \\to (1, 5)$. $\\mathbb{S} = \\{1, 3, 0, 4, 2\\}$ so $\\text{mex}(\\mathbb{S}) = 5$.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9698","tags":["二分","2023","广东","O2优化","省赛/邀请赛"],"sample_group":[["2\n2 3\n1 2 4\n3 0 5\n1 5\n1 3 0 4 2","3\n5"]],"created_at":"2026-03-03 11:09:25"}}