{"raw_statement":[{"iden":"statement","content":"The King of Byteland owns an army of well-trained knights. One day, he decides to attack Hackerland. Hackerland can be described as a grid with N rows and M columns. The cell on the i-th row, j-th column is called cell (i, j) for convenience. The north-west corner is (1, 1) while the south-east corner is (N, M). \n\nIn order to win, the Byteland army must occupy all cells with knights. Now, the King of Byteland has carefully planned the attack. The attack can be divided into two phases. \n\nIn the first phase, a number of knights are sent to some specific cells of Hackerland. \n\nAfter the first phase has ended, the second phase begins. In the second phase, The knights will start attacking the land of Hackerland. Their only way to attack is as follows: If at any moment, there are two knights on the same row or the same column, then all unoccupied cells between the two knights will be under attack, and more knights will be immediately sent to occupy these cells. This phase will end when no more cells can be occupied. \n\nPlease note that the knights are not allowed to move once they are sent to Hackerland.\n\nIn the following graph, the cells (2, 7), (4, 3), (5, 7) and (8, 3) are occupied in the first phase. \n\nWhen the second phase starts, the cells between (4, 3) and (8, 3), (2, 7) and (5, 7) are under attack, and then occupied by other knights. Afterwards, the cells between (4, 3) and (4, 7), (5, 3) and (5, 7) will also be occupied. The second phase will end after this as no more cells can be occupied.\n\nThe attack is currently in the first phase. K cells of Hackerland are already occupied under the command of the King. You, the leader of the knights, are going to send some more knights (possibly none) to some cells of Hackerland of your choice before the second phase starts. \n\nOn one hand, you have to send enough knights to ensure that at the end of the war, all cells are occupied. On the other hand, you have to send as few knights as possible to minimize the chance of being discovered by the army of Hackerland. Your task is to find out the minimum number of knights to be sent.\n\nThe first line contains three integers: N, M and K. (1 ≤ N, M ≤ 100, 0 ≤ K ≤ N·M)\n\nThe next K lines each contains two integers: x and y, which means a knight was sent by the King to occupy cell (x, y). (1 ≤ x ≤ N, 1 ≤ y ≤ M)\n\nNo any two knights are sent to the same cell.\n\nOutput an integer, the minimum number of extra knights to be sent, on a single line.\n\n"},{"iden":"input","content":"The first line contains three integers: N, M and K. (1 ≤ N, M ≤ 100, 0 ≤ K ≤ N·M)The next K lines each contains two integers: x and y, which means a knight was sent by the King to occupy cell (x, y). (1 ≤ x ≤ N, 1 ≤ y ≤ M)No any two knights are sent to the same cell."},{"iden":"output","content":"Output an integer, the minimum number of extra knights to be sent, on a single line."},{"iden":"examples","content":"Input1 1 0Output1Input2 2 0Output4Input3 3 81 11 21 32 12 33 13 23 3Output0"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N, M \\in \\mathbb{Z}^+ $ denote the dimensions of the grid.  \nLet $ K \\in \\mathbb{Z}_{\\geq 0} $ denote the number of initially occupied cells.  \nLet $ S \\subseteq \\{1, \\dots, N\\} \\times \\{1, \\dots, M\\} $ be the set of initially occupied cells, with $ |S| = K $.  \n\n**Constraints**  \n1. $ 1 \\leq N, M \\leq 100 $  \n2. $ 0 \\leq K \\leq N \\cdot M $  \n3. All points in $ S $ are distinct.  \n\n**Objective**  \nFind the minimum number of additional points to add to $ S $, denoted $ T $, such that under the propagation rule — *if two knights share a row or column, all cells between them in that row or column become occupied* — the entire grid $ \\{1, \\dots, N\\} \\times \\{1, \\dots, M\\} $ becomes occupied.  \n\nEquivalently:  \nLet $ \\langle S \\cup T \\rangle $ denote the closure of $ S \\cup T $ under the propagation rule (i.e., the set of all cells eventually occupied).  \nMinimize $ |T| $ such that $ \\langle S \\cup T \\rangle = \\{1, \\dots, N\\} \\times \\{1, \\dots, M\\} $.","simple_statement":"You are given an N×M grid. Some K cells already have knights.  \nIn phase 2, if two knights are in the same row or column, all cells between them get filled automatically.  \nYou can add extra knights before phase 2 starts.  \nFind the minimum number of extra knights needed so that the entire grid gets filled.","has_page_source":false}