게리맨더링

게리맨더링은 특정 정당에게 유리하도록 선거구를 나누는 기법이다. 원래 선거구는 유권자 간 대표성이 대체로 균등하도록 10년에 한 번씩 재검토하게 되어 있다. 그러나 집권 정당은 미래 선거에서 더 많은 의석을 얻기 위한 도구로 선거구 재획정을 활용하곤 한다. 이렇게 하면 많은 유권자의 표가 사실상 사표(死票)가 되어 원래 취지에 어긋나지만, 어쨌든 선거에서 이기기 위해 할 수 있는 일을 하는 셈이다.

게리맨더링을 잘 하려면 최적의 선거구를 계산하는 프로그램이 필요하다. 만들어진 선거구가 “자연스럽게” 보이지 않아도 상관없다. 이 문제에서는 여러 개의 선거 구역(precinct)을 정확히 두 개의 선거구(district)로 나눈다. 프로그램은 특정 정당이 최적의 게리맨더링으로 두 선거구를 모두 이길 수 있는지, 한 선거구만 이길 수 있는지, 아니면 하나도 이길 수 없는지를 판정해야 한다. 각 선거구는 최소한 하나의 구역을 포함해야 하지만, 두 선거구가 같은(또는 비슷한) 수의 구역을 가질 필요는 없다.

어떤 선거구에서 정당 P의 총 득표수가 정당 Q의 총 득표수보다 엄밀히 많을 때 P가 그 선거구를 이긴 것으로 본다. 두 정당의 득표수가 같으면 P가 이긴 것이 아니다.

첫 줄에 입력에 포함된 데이터 집합의 개수 $K$ ($K \ge 1$)가 주어진다. 그 뒤로 아래 형식의 데이터 집합이 $K$개 이어진다.

각 데이터 집합의 첫 줄에는 구역의 수 $n$ ($1 \le n \le 100$)이 주어진다. 이어서 $n$개의 줄에 각 구역 $i$의 정보가 주어지며, 각 줄에는 두 정당 P와 Q에 투표할 것으로 예상되는 유권자 수 $p_i$와 $q_i$가 주어진다. 이 값들은 $0$ 이상 $1000$ 이하이다.

각 데이터 집합에 대해 먼저 Data Set x:를 한 줄에 출력한다. 여기서 $x$는 데이터 집합의 번호(1부터 시작)이다. 그다음 줄에 최적의 게리맨더링으로 정당 P가 이길 수 있는 선거구의 최대 개수($0$, $1$, 또는 $2$)를 출력한다.