E - Intersection Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

N 個の整数集合 S_1, S_2, \dots, S_N があります。
S_i に含まれている整数は C_i 個あり、小さい方から順に A_{i, 1}, \dots, A_{i, C_i} です。
この中から 2 個以上の整数集合を選ぶ方法のうち、次の条件を満たす選び方は何通りありますか？

  • 選んだ集合の共通部分は奇数のみからなる。

ここで、選んだ集合の共通部分とは、全ての選んだ集合に含まれている整数全体からなる集合のことを言います。

制約

  • 2 \leq N \leq 10
  • 1 \leq C_i \leq 10
  • 1 \leq A_{i,1} \lt A_{i,2} \lt \dots \lt A_{i,C_i} \leq 100
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
C_1 A_{1,1} A_{1,2} \dots A_{1,C_1}
C_2 A_{2,1} A_{2,2} \dots A_{2,C_2}
\vdots
C_N A_{N,1} A_{N,2} \dots A_{N,C_N}

出力

答えを出力せよ。

入力例 1

3
3 1 2 5
4 1 3 4 5
2 2 3

出力例 1

3

集合の選び方とその共通部分、および条件を満たすかどうかを全て列挙すると次の通りです。

  • S_1, S_2 の共通部分は \lbrace 1, 5 \rbrace であり、この選び方は条件を満たします。
  • S_1, S_3 の共通部分は \lbrace 2 \rbrace であり、この選び方は条件を満たしません。
  • S_2, S_3 の共通部分は \lbrace 3 \rbrace であり、この選び方は条件を満たします。
  • S_1, S_2, S_3 の共通部分は \lbrace \rbrace (空集合) であり、この選び方は条件を満たします。

共通部分が空集合である場合も条件を満たすのに注意してください。

入力例 2

5
6 4 5 6 9 10 17
5 1 7 9 13 20
6 2 5 8 15 16 20
6 2 5 6 7 16 19
1 3

出力例 2

23

Problem Statement

There are N sets of integers: S_1, S_2, \dots, S_N.
S_i contains C_i integers, A_{i, 1}, \dots, A_{i, C_i}, in ascending order.
Among the ways to choose two or more of the sets, how many of them satisfy the following condition?

  • The intersection of the chosen sets contains only odd numbers.

Here, the intersection of chosen sets is the set consisting of the integers contained in all of the chosen sets.

Constraints

  • 2 \leq N \leq 10
  • 1 \leq C_i \leq 10
  • 1 \leq A_{i,1} \lt A_{i,2} \lt \dots \lt A_{i,C_i} \leq 100
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
C_1 A_{1,1} A_{1,2} \dots A_{1,C_1}
C_2 A_{2,1} A_{2,2} \dots A_{2,C_2}
\vdots
C_N A_{N,1} A_{N,2} \dots A_{N,C_N}

Output

Print the answer.

Sample Input 1

3
3 1 2 5
4 1 3 4 5
2 2 3

Sample Output 1

3

We enumerate the possible choices of sets, their intersections, and whether they satisfy the condition:

  • The intersection of S_1 and S_2 is \lbrace 1, 5 \rbrace, which satisfies the condition.
  • The intersection of S_1 and S_3 is \lbrace 2 \rbrace, which does not satisfy the condition.
  • The intersection of S_2 and S_3 is \lbrace 3 \rbrace, which satisfies the condition.
  • The intersection of S_1, S_2, and S_3 is \lbrace \rbrace (an empty set), which satisfies the condition.

Note that the condition is satisfied even when the intersection is an empty set.

Sample Input 2

5
6 4 5 6 9 10 17
5 1 7 9 13 20
6 2 5 8 15 16 20
6 2 5 6 7 16 19
1 3

Sample Output 2

23