题目描述

一座新的艺术博物馆即将开放！它是一座单层建筑，形状是一个大的等边三角形。这个大三角形由许多相同的小等边三角形房间组成，博物馆的边长是小房间边长的 $S$ 倍。每个房间都通过门与所有共享一条边（不仅仅是顶点）的房间相连。

每个房间由两个数字标识：它所在的行（从上到下计数，从 $1$ 开始），以及在该行中的位置（从左到右计数，从 $1$ 开始）。下图展示了当 $S = 3$ 时房间的连接方式和编号：

:::align{center} :::

Alma 和 Berthe 是正在给博物馆房间涂色的艺术家。Alma 从房间 $(R_A, P_A)$ 开始，Berthe 从另一个不同的房间 $(R_B, P_B)$ 开始。她们都已经涂好了自己的起始房间。博物馆中另有 $C$ 个房间正在施工，Alma 和 Berthe 不得进入或涂刷这些房间。

Alma 和 Berthe 正在进行一场友好的竞争，玩一个回合制游戏，Alma 先手。在一位画家的回合中，如果她当前所在的房间与至少一个未涂色且未施工的房间相邻，则她必须选择其中一个房间，移动过去并涂色。否则，该画家无法移动，并在她的回合中什么也不做。当两位画家都无法移动时，游戏结束。游戏的得分是 Alma 涂色的房间数减去 Berthe 涂色的房间数。

两位画家都做出最优决策，Alma 试图最大化得分，Berthe 试图最小化得分。在这种情况下，无论 Berthe 做什么，Alma 能保证的最佳得分是多少？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含六个整数 $S$、$R_A$、$P_A$、$R_B$、$P_B$ 和 $C$。它们分别是：博物馆的边长（以房间边长为单位）、Alma 起始房间的行和位置、Berthe 起始房间的行和位置，以及正在施工的房间数量。然后有 $C$ 行，第 $i$ 行（从 $1$ 开始计数）包含两个整数 $R_i$ 和 $P_i$，表示第 $i$ 个施工房间的行和位置。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是如上所述的 Alma 能保证的最佳得分。

2
2 1 1 2 1 0
2 2 2 1 1 2
2 1
2 3

Case #1: 2
Case #2: 0

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

Case #1: 0
Case #2: -1

提示

在样例 #1 中，游戏必须按如下进程进行：

• Alma 移动到房间 $(2, 2)$。
• Berthe 无法移动。
• Alma 移动到房间 $(2, 3)$。
• Berthe 仍然无法移动。
• Alma 无法移动。由于两位画家都无法移动，游戏结束。

Alma 涂了 $3$ 个房间，Berthe 涂了 $1$ 个房间，得分为 $3 - 1 = 2$。

在样例 #2 中，两位画家都无法移动。她们只涂了自己的起始房间。

限制条件

$0 \le C \le S^2 - 2$。

$1 \le R_A \le S$。

$1 \le P_A \le 2 \times R_A - 1$。

$1 \le R_B \le S$。

$1 \le P_B \le 2 \times R_B - 1$。

$(R_A, P_A) \ne (R_B, P_B)$。

对于所有 $i$，$1 \le R_i \le S$。

对于所有 $i$，$1 \le P_i \le 2 \times R_i - 1$。

对于所有 $i$，$(R_i, P_i) \ne (R_A, P_A)$。

对于所有 $i$，$(R_i, P_i) \ne (R_B, P_B)$。

对于所有 $i < C$，要么 $R_i < R_{i+1}$，要么 $R_i = R_{i+1}$ 且 $P_i < P_{i+1}$。

测试集 1

$T = 48$。

$S = 2$。

测试集 2

$1 \le T \le 100$。

$2 \le S \le 6$。

翻译由 DeepSeek V4 Pro 完成