Description

一个大小为 $N$ 的排列是一个长度为 $N$ 的序列，其中每个数字都在 $0$ 到 $N-1$ 之间，且每个数字恰好出现一次。它们可以以任意顺序排列。

一共有很多（准确来说是 $N!$ 个，但在本题中这并不重要）大小为 $N$ 的排列。有时候我们希望均匀随机地选出一个排列：即每个排列被选中的概率完全相同。

下面是一个能达到这一目标的算法伪代码（我们在后文称之为 GOOD 算法）：

for k in 0 .. N-1:
  a[k] = k
for k in 0 .. N-1:
  p = randint(k .. N-1)
  swap(a[k], a[p])

在上面的代码中，randint(a .. b) 表示在 $a$ 到 $b$（包括两端）之间均匀随机地选取一个整数。

用文字描述这个算法：我们从一个初始排列开始，即 $0$ 到 $N-1$ 按升序排列。接着，对于每一个 $k$ 从 $0$ 到 $N-1$，我们在区间 $[k, N-1]$ 中随机选择一个整数 $p_k$，然后交换排列中第 $k$ 个位置（从 $0$ 开始编号）和第 $p_k$ 个位置上的元素。

来看一个 $N=4$ 的例子。初始排列为：

当 $k=0$ 时，我们在 $0$ 到 $3$ 之间随机选择 $p_0$，假设选中 $2$。交换第 $0$ 个和第 $2$ 个元素，排列变为：

接着 $k=1$，在 $1$ 到 $3$ 之间随机选择 $p_1$，假设选中 $2$。交换第 $1$ 个和第 $2$ 个元素，排列变为：

当 $k=2$ 时，在 $2$ 到 $3$ 之间随机选择 $p_2$，假设选中 $3$。交换第 $2$ 个和第 $3$ 个元素，排列变为：

当 $k=3$ 时，只能选 $3$，交换第 $3$ 个和第 $3$ 个元素，排列不变：

至此，生成的随机排列结束。

还有许多其他算法可以生成均匀随机的排列。然而，也存在很多与上面算法看似相似，但并不均匀的算法——这些算法生成某些排列的概率会比其他排列高。

下面给出一个此类「坏」算法（我们在后文称之为 BAD 算法）。它与 GOOD 算法非常相似，但在每一步中，$p_k$ 不再从 $[k, N-1]$ 区间中选择，而是从 $[0, N-1]$ 区间中随机选择。这看似是一个小改动，但结果是某些排列会更容易被生成！

下面是该算法的伪代码：

for k in 0 .. N-1:
  a[k] = k
for k in 0 .. N-1:
  p = randint(0 .. N-1)
  swap(a[k], a[p])

在每个测试用例中，你会获得一个由以下方式生成的排列：首先，我们以 $50\%$ 的概率选择 GOOD 算法或 BAD 算法，然后使用选中的算法生成一个排列。你需要根据给定的排列，猜测它是由哪个算法生成的。

这道题在 Code Jam 中比较特别。你将会得到 $T = 120$ 个大小为 $N = 1000$ 的排列，并需要为每个排列输出一个答案——这部分流程是常规的。然而，你并不需要全部答对！只要你猜对至少 $G = 109$ 个测试用例，整体答案就会被判定为正确。但无论是否正确，你仍需按照格式输出所有答案。如果出错，唯一允许的错误是把 GOOD 错猜成 BAD 或反之；但是对于每个测试用例，你都必须打印 "GOOD" 或 "BAD"。

保证给出的每个排列都严格按照上述方法独立生成。

这道题涉及随机性，因此即使是最优策略，也有可能在某次提交中因为概率原因导致答对数不足 $109$ 个而失败。如果发生这种情况，可以再次提交相同的策略尝试，因为每次重新提交可能运气不同。不过注意，若因为错误提交而重新提交，即使仅仅是运气导致错误，也会产生常规的 4 分钟罚时。

在我们的经验中，确实出现过由于概率原因导致答案错误的情况；因此，如果你确信自己的方案正确，但未通过，合理的策略是再次尝试相同方案。

祝你好运！

Input Format

输入的第一行是测试用例数 $T$（始终为 $120$）。每个测试用例包含两行：第一行是单个整数 $N$（始终为 $1000$），第二行是 $N$ 个用空格分隔的整数，表示一个由两种算法之一生成的排列。

Output Format

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 "GOOD" 或 "BAD"（不包含引号）。若你猜测该排列由题目中第一个描述的算法（GOOD 算法）生成，则输出 "GOOD"；否则输出 "BAD"。

2
3
0 1 2
3
2 0 1

Case #1: BAD
Case #2: GOOD

Hint

样例说明

示例输入不符合题面中的大小限制——实际测试输入会更大。

限制条件（45 分）

• $T = 120$
• $G = 109$
• $N = 1000$
• 每个排列中的数字都在 $0$ 到 $N-1$ 之间，且 $0$ 到 $N-1$ 每个数字恰好出现一次。

翻译由 ChatGPT-4o 完成。