Move, ant! (pt 2)
After randomly picking out obstacles, the ant still couldn't crawl to the last row. Koi wonders what is the smallest amount of obstacles he has to pick so that the ant is able to crawl to the top (last row)?
The first line contains an integer, the number of testcases in the test.
The descriptions of testcases follow.
Each description begins with a line that contains two integer \(n\) \((3 \le n)\) and \(k\) \((1 \le k < (n - 1)^2)\), the size of the table and the number of obstacles Koi picked up, respectively. This is followed by \(k\) lines, each line contains two integers \(r\) and \(c\) \((2 \le r \le n - 1, 1 \le c \le n)\), the position (row, column) of the obstacles.
It is guaranteed that the sum of \(n\) over all input testcases does not exceed \(1000\), and the position of obstacles are different.
For each testcase, output a natural number in one line.
1 5 3 2 2 3 2 3 3
Explanation: Koi need to pick up 1 more obstacle in row 4 column 2 or row 4 column 3 so that the ant can crawl to the last row.