공과 구멍

시간 제한0.5초메모리 제한512 MB

요약

정수 집합 n개가 주어질 때, S_i의 공을 S_j의 반정수 위치 구멍으로 밀어 넣었을 때 홀수 개의 구멍이 채워지는 쌍 (i<j)의 개수를 센다.

난이도: 어려움10점 중 8점
유형: 조합론, 비트 연산, 수학, 해시맵
정답자: 아직 제출이 없습니다

문제

Bobo는 게임을 하나 만들어서 계속 플레이한다.

게임 $({a_1, a_2, \dots, a_m}, {b_1, b_2, \dots, b_l})$ 은 수직선 위에서 진행된다. 먼저 bobo는 $a_1, a_2, \dots, a_m$ 위치에 각각 공 $m$ 개를 놓는다. 그다음 bobo는 $b_1 + 0.5, b_2 + 0.5, \dots, b_l + 0.5$ 위치에 구멍 $l$ 개를 판다. 마지막으로 bobo는 모든 공을 앞으로 밀어서 공이 구멍에 빠지도록 한다. 공이 하나 이상 들어 있는 구멍의 개수가 홀수일 때, 그리고 그때만 bobo가 이긴다.

이제 bobo에게는 $n$ 개의 집합 $S_1, S_2, \dots, S_n$ 이 있고, $(S_i, S_j)$ $(i < j)$ 형태의 게임 중에서 그가 이길 수 있는 게임이 몇 개인지 알고 싶어 한다.

입력

첫 번째 줄에 정수 $n$ 이 주어진다 ( $2 \leq n \leq 5000$ ).

다음 $n$ 개의 줄 각각에는 정수 $k_i$ 가 주어지고, 이어서 집합 $S_i$ 를 나타내는 서로 다른 정수 $S_{i, 1}, S_{i, 2}, \dots, S_{i, k_i}$ 가 주어진다 ( $1 \leq k_i \leq 50, 1 \leq S_{i, j} \leq 50$ ). $k_i$ 는 $S_i$ 의 크기이다.

출력

bobo가 이길 수 있는 게임의 수를 나타내는 정수 하나를 출력한다.

예제2

예제 1
입력
```
2
1 1
2 1 2
```
예상 출력
```
1
```
예제 2
입력
```
2
2 1 2
2 2 1
```
예상 출력
```
0
```