P8108 [Cnoi2021] Tales of Cyansis Pearl

Cirno made a new game called “Tales of Cyansis Pearl”. Game example (Sample #1): 

The rules are as follows: At the beginning, there is an $n \times n$ grid, and each cell contains one Cyansis Pearl. There are $n$ colors in total. For each color, there are exactly $n$ pearls, distributed **uniformly at random** in the $n \times n$ grid. Each time, the player may choose several consecutive pearls of the same color on the bottom row of the grid and remove them. After removal, the pearls above will fall down due to gravity. The player repeats the above operation until all pearls are removed. Then the game ends. Now, Cirno gives you a **uniformly random** initial board of the game Tales of Cyansis Pearl. Find the minimum number of moves to finish the game.

The first line contains an integer $n$. The following $n$ lines each contain $n$ integers, each in the range $[1, n]$. It is guaranteed that each integer appears exactly $n$ times.

Output one line containing an integer, the minimum number of moves.

For $100\%$ of the testdata, $1 \le n \le 1000$. The input is guaranteed to be **randomly generated**. Reprinted from XDUCPC 2021 Onsite Contest J. Translated by ChatGPT 5