Last Step With a Top-to-Bottom Path

You are given two integers rows and cols and a two-dimensional list of integers blocked. Consider a grid with rows rows and cols columns. Every cell starts open.

Each element in blocked contains [r, c] meaning the cell in row r and column c becomes blocked. Rows and columns are numbered from 1. The cells become blocked one per step, in the order listed: on step 1 the cell blocked[0] becomes blocked, on step 2 the cell blocked[1] becomes blocked, and so on. You can assume blocked lists every cell of the grid exactly once.

A top-to-bottom path is a sequence of open cells that starts at any cell in row 1, ends at any cell in row rows, and only moves between cells that share a side (up, down, left, or right).

Return the largest step t such that a top-to-bottom path still exists after the first t cells have become blocked.

Examples

Example 1

Input: rows = 2, cols = 2, blocked = [[1,1],[2,1],[1,2],[2,2]]
Output: 2
Explanation: After step 2 the cells [1,1] and [2,1] are blocked. The open cells [1,2] and [2,2] share a side and join row 1 to row 2. After step 3 the only open cell is [2,2], which is not in row 1, so no path exists.

Example 2

Input: rows = 2, cols = 2, blocked = [[1,1],[1,2],[2,1],[2,2]]
Output: 1
Explanation: After step 1 the open cells [1,2] and [2,2] form a path. After step 2 both cells of row 1 are blocked, so no path can start.

Example 3

Input: rows = 3, cols = 3, blocked = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]
Output: 3
Explanation: After step 3 the cells [1,2], [2,1], and [3,3] are blocked. The open cells [1,3], [2,3], [2,2], [3,2] form a path from row 1 to row 3. After step 4 the cell [2,2] is blocked as well, and no path remains.