A - 共通の好きな曲 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 266 点

問題文

高橋君は音楽サークルの部長です。高橋君を除くサークルのメンバーは N 人います。

今度のサークル活動で演奏する曲を決めるため、高橋君は 1 番から M 番までの番号が付けられた M 曲の候補リストを用意しました。N 人のメンバーはそれぞれ、このリストの中から自分が演奏したい曲を 1 曲以上選び（同じ曲を複数回選ぶことはありません）、高橋君に報告しました。なお、高橋君自身は曲を選びません。

i 番目のメンバー (1 \leq i \leq N) は K_i 曲を選び、選んだ曲の番号は C_{i,1}, C_{i,2}, \ldots, C_{i,K_i} でした。

N 人のメンバー全員が共通して選んだ曲の個数を求めてください。すなわち、1 番から M 番までの曲のうち、N 人全員が選んでいる曲がいくつあるかを出力してください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq K_i \leq M
  • 1 \leq C_{i,1} < C_{i,2} < \cdots < C_{i,K_i} \leq M（各メンバーが選んだ曲の番号は相異なり、狭義昇順で与えられる）
  • \sum_{i=1}^{N} K_i \leq 2 \times 10^5
  • 入力はすべて整数

入力

N M
K_1 C_{1,1} C_{1,2} \ldots C_{1,K_1}
K_2 C_{2,1} C_{2,2} \ldots C_{2,K_2}
\vdots
K_N C_{N,1} C_{N,2} \ldots C_{N,K_N}
  • 1 行目には、メンバーの人数 N と、候補リストの曲数 M が、スペース区切りで与えられる。
  • 第 (i+1) 行目 (1 \leq i \leq N) には、i 番目のメンバーが選んだ曲の数 K_i と、選んだ曲の番号 C_{i,1}, C_{i,2}, \ldots, C_{i,K_i} が、スペース区切りで与えられる。曲の番号は狭義昇順に並んでいる。

出力

N 人のメンバー全員が共通して選んだ曲の個数を 1 行で出力せよ。

入力例 1

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

出力例 1

2

入力例 2

4 10
5 1 3 5 7 9
3 2 4 6
4 1 3 5 7
6 1 2 3 5 7 9

出力例 2

0

入力例 3

5 100
10 5 10 20 30 40 50 60 70 80 90
8 5 10 20 30 50 70 80 90
12 1 5 10 15 20 25 30 50 70 80 90 100
6 5 10 30 50 70 90
9 5 10 20 30 50 60 70 80 90

出力例 3

6

Score : 266 pts

Problem Statement

Takahashi is the leader of a music club. There are N members in the club, excluding Takahashi.

To decide which songs to perform at the next club activity, Takahashi prepared a candidate list of M songs numbered from 1 to M. Each of the N members selected one or more songs they want to perform from this list (without selecting the same song more than once) and reported their choices to Takahashi. Note that Takahashi himself does not select any songs.

The i-th member (1 \leq i \leq N) selected K_i songs, and the numbers of the selected songs were C_{i,1}, C_{i,2}, \ldots, C_{i,K_i}.

Find the number of songs that were selected by all N members in common. In other words, among the songs numbered from 1 to M, output how many songs were selected by all N members.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq K_i \leq M
  • 1 \leq C_{i,1} < C_{i,2} < \cdots < C_{i,K_i} \leq M (The song numbers selected by each member are distinct and given in strictly ascending order)
  • \sum_{i=1}^{N} K_i \leq 2 \times 10^5
  • All input values are integers

Input

N M
K_1 C_{1,1} C_{1,2} \ldots C_{1,K_1}
K_2 C_{2,1} C_{2,2} \ldots C_{2,K_2}
\vdots
K_N C_{N,1} C_{N,2} \ldots C_{N,K_N}
  • The first line contains the number of members N and the number of songs in the candidate list M, separated by a space.
  • The (i+1)-th line (1 \leq i \leq N) contains the number of songs selected by the i-th member K_i, followed by the numbers of the selected songs C_{i,1}, C_{i,2}, \ldots, C_{i,K_i}, separated by spaces. The song numbers are listed in strictly ascending order.

Output

Output in one line the number of songs that were selected by all N members in common.

Sample Input 1

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

Sample Output 1

2

Sample Input 2

4 10
5 1 3 5 7 9
3 2 4 6
4 1 3 5 7
6 1 2 3 5 7 9

Sample Output 2

0

Sample Input 3

5 100
10 5 10 20 30 40 50 60 70 80 90
8 5 10 20 30 50 70 80 90
12 1 5 10 15 20 25 30 50 70 80 90 100
6 5 10 30 50 70 90
9 5 10 20 30 50 60 70 80 90

Sample Output 3

6