{"problem":{"name":"[GDCPC 2023] Peg Solitaire","description":{"content":"$\\textit{Peg Solitaire}$ is a single-player boardgame on a chessboard with $n$ rows and $m$ columns. Each cell of the chessboard either is empty, or contains a chesspiece. Initially, there are $k$ che","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9700"},"statements":[{"statement_type":"Markdown","content":"$\\textit{Peg Solitaire}$ is a single-player boardgame on a chessboard with $n$ rows and $m$ columns. Each cell of the chessboard either is empty, or contains a chesspiece. Initially, there are $k$ chesspieces on the chessboard.\n\nDuring the game, the player can choose a chesspiece, jump it over an adjacent chesspiece into an empty cell, and finally remove the chesspiece which is jumped over. More precisely, let $(i, j)$ be the cell on the $i$-th row and the $j$-th column, the player can perform operations of the following four types.\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/ugauif68.png)\n\nGiven the initial state of the chessboard, the player can perform the operations any number of times (including zero times). Calculate the minimum possible number of chesspieces remaining on the chessboard.\n\n## Input\n\nThere are multiple test cases. The first line of the input contains an integer $T$ ($1 \\le T \\le 20$) indicating the number of test cases. For each test case:\n\nThe first line contains three integers $n$, $m$ and $k$ ($1 \\le n, m \\le 6$, $1 \\le k \\le \\min(6, n \\times m)$) indicating the number of rows and columns of the chessboard and the initial number of chesspieces.\n\nFor the following $k$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($1 \\le x_i \\le n$, $1 \\le y_i \\le m$) indicating that there is a chesspiece in the cell on the $x_i$-th row and the $y_i$-th column at the beginning. Except from these $k$ cells, all other cells are empty at the beginning. The positions of these $k$ cells contain no duplicate.\n\n## Output\n\nFor each test case output one line containing one integer indicating the minimum possible number of chesspieces remaining on the chessboard.\n\n[samples]\n\n## Note\n\nThe first sample test case is explained as follows.\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/aragowha.png)\n\nFor the second sample test case, as the chessboard does not contain empty cell at the beginning, the player cannot perform any operation.\n\nFor the third sample test case, as the chessboard has less than three cells, the player cannot perform any operation.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9700","tags":["搜索","2023","广东","O2优化","枚举","省赛/邀请赛"],"sample_group":[["3\n3 4 5\n2 2\n1 2\n1 4\n3 4\n1 1\n1 3 3\n1 1\n1 2\n1 3\n2 1 1\n2 1","2\n3\n1"]],"created_at":"2026-03-03 11:09:25"}}