题目描述

给你一个 $n$ 行 $m$ 列的国际象棋棋盘。最初棋盘上有 $k$ 个红色骑士（骑士是国际象棋中的马），你需要在每个格子上放置一个骑士，并为其选择一种颜色：白色或黑色（红色骑士的位置与颜色在输入中已给出，剩余格子由你填白或黑）。每个格子恰好放一个骑士。

骑士的走法为“日”字：若骑士在 $(x_1,y_1)$，则它可以攻击 $(x_2,y_2)$ 当且仅当满足任一条件：

• $|x_1-x_2|=2$ 且 $|y_1-y_2|=1$，或
• $|x_1-x_2|=1$ 且 $|y_1-y_2|=2$。

下面是一些骑士可以攻击哪些格子的示例。在下图中，如果骑士当前在蓝色格子，则它可以攻击所有红色格子（且仅能攻击这些格子）。

定义一次 骑士对决 为一对不同颜色的骑士互相攻击（即两个格子上的骑士颜色不同且位置互为骑士可攻击的位置）。

你的目标是：在剩余格子中任意选择白/黑两色放置骑士，使得骑士对决的总数最大化。输出这个最大值。

输入格式

输入包含多组测试数据。

• 第一行包含一个整数 $t$，表示测试数据组数。

• 对于每组测试数据：

  • 第一行包含三个整数 $n, m, k$，表示棋盘为 $n\times m$，初始有 $k$ 个红色骑士。
  • 接下来 $k$ 行，每行两个整数 $x,y$（$1\le x\le n,\ 1\le y\le m$），表示棋盘上在位置 $(x,y)$ 放有一个红色骑士。保证没有两个红色骑士放在同一格。

坐标系约定：行号 $x$ 从 $1$ 到 $n$，列号 $y$ 从 $1$ 到 $m$。

输出格式

对于每组测试数据，输出一行，包含一个整数：在最优填色方案下，最多可能产生的骑士对决对数。

样例输入 1

2
2 4 3
1 1
1 4
2 1
2 3 1
2 3

样例输出 1

4
2

说明

样例解释

一个可能的最优布置（颜色用 $R =$ 红，$B=$ 黑，$W=$ 白 表示两种你可选颜色中的一种）如下图示（示意）可以得到 $4$ 对骑士对决，例如：

• $(1,1)$ 的红骑士攻击 $(2,3)$ 的黑骑士；
• $(1,3)$ 的黑骑士攻击 $(2,1)$ 的红骑士；
• $(1,2)$ 的黑骑士攻击 $(2,4)$ 的白骑士；
• $(1,4)$ 的红骑士攻击 $(2,2)$ 的白骑士。

样例 2

见选手目录下的 chess/chess2.in 与 chess/chess2.ans。 该测试用例满足测试点 $1\sim 3$ 的约束条件。

样例 3

见选手目录下的 chess/chess3.in 与 chess/chess3.ans。 该测试用例满足测试点 $4\sim 5$ 的约束条件。

样例 4

见选手目录下的 chess/chess4.in 与 chess/chess4.ans。 该测试用例满足测试点 $6\sim 7$ 的约束条件。

样例 5

见选手目录下的 chess/chess5.in 与 chess/chess5.ans。 该测试用例满足测试点 $8\sim 10$ 的约束条件。

数据范围

对于 $100\%$ 的数据，满足：

• $1\le t\le 10$；
• $1\le n,m\le 100$；
• $0\le k\le n\times m$。

保证没有两个红色骑士在同一格子上。

各测试点的附加限制如下表所示：

大样例

点击下载