2069B.md (1980B)
1 Source: https://codeforces.com/problemset/problem/2069/B 2 3 B. Set of Strangers 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a table of $n$ rows and $m$ columns. Initially, the cell at the $i$-th row and the $j$-th column has color $a_{i, j}$. 22 23 Let's say that two cells are strangers if they don't share a side. Strangers are allowed to touch with corners. 24 25 Let's say that the set of cells is a set of strangers if all pairs of cells in the set are strangers. Sets with no more than one cell are sets of strangers by definition. 26 27 In one step, you can choose any set of strangers such that all cells in it have the same color and paint all of them in some other color. You can choose the resulting color. 28 29 What is the minimum number of steps you need to make the whole table the same color? 30 31 Input 32 33 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Next, $t$ cases follow. 34 35 The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le m \le 700$) — the number of rows and columns in the table. 36 37 The next $n$ lines contain the colors of cells in the corresponding row $a_{i, 1}, \dots, a_{i, m}$ ($1 \le a_{i, j} \le nm$). 38 39 It's guaranteed that the total sum of $nm$ doesn't exceed $5 \cdot 10^5$ over all test cases. 40 41 Output 42 43 For each test case, print one integer — the minimum number of steps to paint all cells of the table the same color. 44 45 Example 46 47 Input 48 49 ``` 50 4 51 52 1 1 53 54 1 55 56 3 3 57 58 1 2 1 59 60 2 3 2 61 62 1 3 1 63 64 1 6 65 66 5 4 5 4 4 5 67 68 3 4 69 70 1 4 2 2 71 72 1 4 3 5 73 74 6 6 3 5 75 ``` 76 77 Output 78 79 ``` 80 0 81 2 82 1 83 10 84 ``` 85 86 Note 87 88 In the first test case, the table is painted in one color from the start. 89 90 In the second test case, you can, for example, choose all cells with color $1$ and paint them in $3$. Then choose all cells with color $2$ and also paint them in $3$. 91 92 In the third test case, you can choose all cells with color $5$ and paint them in color $4$.