올바른 셔플 (Small)

크기가 $N$인 순열은 0 이상 $N-1$ 이하의 각 수가 정확히 한 번씩 나타나는 길이 $N$의 수열입니다. 수들은 어떤 순서로 나열되어도 됩니다.

크기가 $N$인 순열은 $N!$개 있지만, 이 문제에서는 그 개수가 중요하지 않습니다. 순열을 하나 무작위로 고르고 싶을 때가 있고, 이때는 균일하게, 즉 모든 순열이 같은 확률로 뽑히도록 고르고 싶습니다.

아래는 그 목표를 이루는 알고리즘 중 하나의 의사 코드입니다. 이를 좋은 알고리즘이라고 부르겠습니다.

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$인 경우를 예로 들어 보겠습니다. 항등 순열 0 1 2 3에서 시작합니다. $k=0$일 때 $p_0$를 0에서 3 사이에서 뽑았더니 2가 나왔다고 합시다. 위치 0과 2의 원소를 바꾸면 2 1 0 3이 됩니다. $k=1$일 때 $p_1$을 1에서 3 사이에서 뽑았더니 다시 2가 나왔다고 합시다. 위치 1과 2의 원소를 바꾸면 2 0 1 3이 됩니다. $k=2$일 때 $p_2$를 2에서 3 사이에서 뽑았더니 3이 나왔다고 합시다. 위치 2와 3의 원소를 바꾸면 2 0 3 1이 됩니다. $k=3$일 때는 선택지가 3 하나뿐이어서 바꿔도 순열이 달라지지 않습니다. 최종 순열은 2 0 3 1입니다.

일부 알고리즘은 좋은 알고리즘과 거의 같아 보이지만 균일하지 않아서, 어떤 순열은 다른 순열보다 더 자주 나옵니다. 이런 나쁜 알고리즘 중 하나는 좋은 알고리즘에서 한 가지만 바꿉니다. 각 단계에서 $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% 확률로 고릅니다. 그다음 고른 알고리즘으로 순열을 생성합니다. 순열만 보고 어떤 알고리즘이 선택되었는지 맞힐 수 있을까요?

이 문제는 Code Jam 문제치고는 조금 특이합니다. 각각 $N = 1000$개의 수로 이루어진 순열이 $T = 120$개 주어지고, 각 순열마다 답을 출력해야 합니다. 모든 답이 맞을 필요는 없습니다. 적어도 $G = 109$개의 답이 맞으면 정답으로 인정됩니다. 다만 답이 틀리더라도 출력 형식은 반드시 지켜야 합니다. 맞지 않아도 정답으로 인정될 수 있는 경우는 GOOD과 BAD를 서로 바꾼 경우뿐이며, 그래도 각 케이스마다 GOOD 또는 BAD 중 하나를 출력해야 합니다.

순열은 위 방법에 따라 생성되었으며 서로 독립적으로 만들어졌다고 보장됩니다. 무작위성 때문에, 가장 좋은 풀이라도 어떤 입력에서는 109개의 정답을 맞히지 못할 수 있습니다. 두 알고리즘 모두 임의의 순열을 만들 수 있기 때문입니다. 그래서 이 문제에는 Large 입력 없이 Small 입력만 있으며, 운이 나빴다고 생각되면 다시 제출할 수 있습니다. 나중에 정답을 맞히더라도, 운 때문에 틀렸던 제출에는 보통 4분의 패널티가 붙습니다.

실제로 운 때문에 틀리는 일이 있었습니다. 풀이가 맞다고 확신하는데 실패했다면 같은 풀이를 다시 제출해 보는 것도 합리적인 방법입니다.

첫 줄에는 테스트 케이스 수 $T$가 주어집니다. $T$는 항상 120입니다. 각 테스트 케이스는 두 줄로 이루어집니다. 첫 줄에는 정수 $N$이 주어지며, $N$은 항상 1000입니다. 다음 줄에는 공백으로 구분된 $N$개의 정수가 주어지는데, 이것이 두 알고리즘 중 하나로 생성된 순열입니다.

각 테스트 케이스마다 "Case #x: y" 형식의 한 줄을 출력합니다. $x$는 1부터 시작하는 테스트 케이스 번호입니다. $y$는 첫 번째 알고리즘으로 생성되었다고 판단하면 GOOD, 두 번째 알고리즘으로 생성되었다고 판단하면 BAD입니다.

• $T = 120$
• $G = 109$
• $N = 1000$
• 각 수는 0 이상 $N-1$ 이하이며, 0부터 $N-1$까지의 각 수가 순열에 정확히 한 번씩 나타납니다.

예제 입력은 문제의 제한 조건을 따르지 않습니다. 실제 입력은 훨씬 큽니다.