P13474 [GCJ 2008 APAC SemiFinal] What are Birds?

你正在研究森林中的动物，并试图判断哪些动物是鸟，哪些不是鸟。 你通过测量每只动物的身高和体重来进行判断。要成为一只鸟，动物的身高需要在某个范围内，体重也需要在另一个范围内，但你并不确定这两个范围具体是多少。你还知道，所有满足这两个范围的动物一定是鸟。 你已经将部分测量过的动物展示给生物学家，他们告诉你哪些是鸟，哪些不是。这为你提供了一些关于鸟类身高和体重范围的信息。对于剩下的动物，你的程序需要判断它们是否一定是鸟、一定不是鸟，或者根据已有信息无法确定。

第一行包含一个整数 $C$，表示测试用例的数量。 接下来对于每个测试用例： - 第一行包含一个整数 $N$，表示你已经展示给生物学家的动物数量。 - 接下来的 $N$ 行，每行格式为 "H W X"，其中 $H$ 表示动物的身高，$W$ 表示动物的体重，$X$ 为字符串 "BIRD" 或 "NOT BIRD"。所有数字均为正整数。 - 接下来一行包含一个整数 $M$，表示你未展示给生物学家的动物数量。 - 接下来的 $M$ 行，每行格式为 "H W"，其中 $H$ 表示动物的身高，$W$ 表示动物的体重。所有数字均为正整数。

对于每个测试用例： - 输出一行，格式为 "Case #$X$: "，其中 $X$ 为测试用例编号，从 1 开始。 - 接下来 $M$ 行，每行输出 "BIRD"、"NOT BIRD" 或 "UNKNOWN"（不包含引号），分别表示该动物一定是鸟、一定不是鸟或无法确定。

**样例解释** 第 $1$ 组： 动物 “1500 1500” 必然在鸟类的范围内，因为我们知道身高和体重的范围都包含 $1000$ 和 $2000$。 动物 “900 900” 可能是鸟，也可能不是；我们无法确定身高和体重的范围是否包含 $900$。 动物 “1400 2020” 的身高在鸟类范围内，但如果体重 $2020$ 也在范围内，那么 “1500 2010” 这只我们已知不是鸟的动物也必须在体重范围内。 第 $2$ 组： 在这种情况下，我们知道鸟的身高必须是 $501$。但我们只知道鸟的体重范围包含 $700$，其他不确定。 第 3 组： 在这种情况下，我们知道身高 $100$ 且体重 $100$ 的动物不是鸟，但我们对鸟的范围一无所知。 **数据范围** - $1 \leq C \leq 10$ - $1 \leq$ 所有身高和体重 $\leq 1000000$ **小数据集（5 分，测试点 1 - 可见）** - $1 \leq N \leq 10$ - $1 \leq M \leq 10$ **大数据集（12 分，测试点 2 - 隐藏）** - $1 \leq N \leq 1000$ - $1 \leq M \leq 1000$ 由 ChatGPT 4.1 翻译