33843번 - ∀nnihilation

문제

다각형으로 게임을 해 보자!

처음에 $xy$평면에 1ドル$번부터 $N$번까지 $N$개의 단순 다각형이 주어진다. $i$번 다각형은 꼭짓점이 $c_i$개이고, 각 꼭짓점의 좌표는 반시계 방향으로 $(x_{i 1}, y_{i 1}),ドル $(x_{i 2}, y_{i 2}),ドル $\cdots,ドル $(x_{i c_i}, y_{i c_i})$이다. 두 플레이어는 자신의 차례에 아래와 같은 행동 중 하나를 할 수 있다.

• 누구에게도 선택되지 않은 다각형 하나를 선택해 $x$축을 기준으로 대칭 이동한다.
• 누구에게도 선택되지 않은 다각형 하나를 선택해 $y$축을 기준으로 대칭 이동한다.

자신의 차례를 마쳤을 때, 평행 이동하여 일치하는 두 다각형이 존재한다면 그 두 다각형은 소멸한다. 이후 소멸한 두 다각형은 선택할 수 없다.

자신의 차례에 어떠한 행동도 할 수 없는 플레이어가 패배한다.

두 플레이어가 최선을 다해 게임을 플레이했을 때 누가 이길지 계산해 보자.

입력

첫 번째 줄에 단순 다각형의 개수 $N$이 주어진다. $(1 \le N \le 3,333円)$

두 번째 줄부터 $N$개의 줄에 걸쳐 단순 다각형의 정보가 주어진다. 그중 $i$번째 줄에는 $i$번 다각형의 꼭짓점의 개수 $c_i$와, 각 꼭짓점의 좌표를 나타내는 정수 $x_{i 1},ドル $y_{i 1},ドル $x_{i 2},ドル $y_{i 2},ドル $\cdots,ドル $x_{i c_i},ドル $y_{i c_i}$가 공백으로 구분되어 주어진다. $(3 \le c_i \le 10,000円;$ $-10^9 \le x_{i j}, y_{i j} \le 10^9)$

모든 다각형의 꼭짓점의 개수의 합은 10ドル,000円$ 이하이다.

처음에 평행 이동하여 일치하는 두 다각형이 존재하는 경우는 주어지지 않는다. 서로 다른 다각형끼리 겹칠 수 있음에 유의하라.

출력

첫 번째 줄에 선공이 이긴다면 1을, 후공이 이긴다면 0을 출력한다.

제한

힌트