/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 266 点
問題文
高橋君は大学の研究支援センターで働いています。大学には N 個の研究室があり、それぞれの研究室はいくつかの研究テーマに取り組んでいます。研究室 i（1 \leq i \leq N）は M_i 個の研究テーマに取り組んでおり、それらのテーマはそれぞれ英小文字からなる文字列 W_{i,1}, W_{i,2}, \ldots, W_{i,M_i} で表されます。なお、同じ研究室内で同じ研究テーマが複数回現れることはありません。
大学では、共同研究を促進するために、「共同研究可能」な研究室のペアを調査することになりました。研究室 i が取り組んでいる研究テーマの集合を S_i = \{W_{i,1}, W_{i,2}, \ldots, W_{i,M_i}\} とします。2つの研究室 i, j（i \neq j）が「共同研究可能」であるとは、S_i と S_j に共通して含まれる研究テーマの数が K 個以上であること、すなわち |S_i \cap S_j| \geq K が成り立つことを指します。ここで、2つの研究テーマが同一であるかどうかは、テーマを表す文字列が完全に一致するかどうかで判定します。
高橋君は各研究室が取り組んでいる研究テーマのリストを持っています。これらの情報をもとに、「共同研究可能」な研究室のペアの数を求めてください。ただし、研究室 i と研究室 j のペアと研究室 j と研究室 i のペアは同一のペアとみなし、1 \leq i < j \leq N を満たす (i, j) の組のうち条件を満たすものの個数を答えてください。
制約
- 2 \leq N \leq 500
- 1 \leq K \leq 50
- 1 \leq M_i \leq 50（1 \leq i \leq N）
- W_{i,j} は英小文字のみからなる長さ 1 以上 20 以下の文字列である（1 \leq i \leq N, 1 \leq j \leq M_i）
- 同じ研究室内で同じ研究テーマが複数回現れることはない（すなわち、j \neq k ならば W_{i,j} \neq W_{i,k}）
入力
入力は以下の形式で標準入力から与えられる。
N K
M_1
W_{1,1} W_{1,2} \ldots W_{1,M_1}
M_2
W_{2,1} W_{2,2} \ldots W_{2,M_2}
\vdots
M_N
W_{N,1} W_{N,2} \ldots W_{N,M_N}
最初の行には、研究室の数 N と「共同研究可能」の判定に用いる閾値 K が、スペース区切りで与えられる。
続いて、各研究室 i（i = 1, 2, \ldots, N）について、以下の 2 行が順に与えられる。
- 第 1 行には、研究室 i が取り組んでいる研究テーマの数 M_i が与えられる。
- 第 2 行には、研究室 i が取り組んでいる M_i 個の研究テーマを表す文字列 W_{i,1}, W_{i,2}, \ldots, W_{i,M_i} がスペース区切りで与えられる。
出力
「共同研究可能」な研究室のペアの数を 1 行で出力してください。
入力例 1
3 2 3 ai ml data 4 ml data web security 2 ai ml
出力例 1
2
入力例 2
4 1 3 biology chemistry physics 2 chemistry medicine 4 physics math statistics chemistry 3 biology ecology environment
出力例 2
4
入力例 3
5 3 5 deeplearning nlp vision robotics optimization 4 nlp vision speech recognition 6 deeplearning nlp vision gan transformer diffusion 3 robotics control automation 5 nlp vision deeplearning bert attention
出力例 3
3
Score : 266 pts
Problem Statement
Takahashi works at the university's research support center. The university has N laboratories, and each laboratory is working on several research themes. Laboratory i (1 \leq i \leq N) is working on M_i research themes, each represented by a string of lowercase English letters W_{i,1}, W_{i,2}, \ldots, W_{i,M_i}. Note that the same research theme does not appear more than once within the same laboratory.
To promote collaborative research, the university has decided to investigate pairs of laboratories that are "eligible for collaboration." Let S_i = \{W_{i,1}, W_{i,2}, \ldots, W_{i,M_i}\} be the set of research themes that laboratory i is working on. Two laboratories i, j (i \neq j) are said to be "eligible for collaboration" if the number of research themes common to both S_i and S_j is at least K, that is, |S_i \cap S_j| \geq K holds. Here, whether two research themes are identical is determined by whether their representing strings match exactly.
Takahashi has the list of research themes each laboratory is working on. Based on this information, find the number of pairs of laboratories that are "eligible for collaboration." Note that the pair of laboratory i and laboratory j is considered the same as the pair of laboratory j and laboratory i. Count the number of pairs (i, j) satisfying 1 \leq i < j \leq N that meet the condition.
Constraints
- 2 \leq N \leq 500
- 1 \leq K \leq 50
- 1 \leq M_i \leq 50 (1 \leq i \leq N)
- W_{i,j} is a string of length between 1 and 20 consisting only of lowercase English letters (1 \leq i \leq N, 1 \leq j \leq M_i)
- The same research theme does not appear more than once within the same laboratory (that is, if j \neq k then W_{i,j} \neq W_{i,k})
Input
The input is given from standard input in the following format.
N K
M_1
W_{1,1} W_{1,2} \ldots W_{1,M_1}
M_2
W_{2,1} W_{2,2} \ldots W_{2,M_2}
\vdots
M_N
W_{N,1} W_{N,2} \ldots W_{N,M_N}
The first line contains the number of laboratories N and the threshold K used for determining "eligibility for collaboration," separated by a space.
Then, for each laboratory i (i = 1, 2, \ldots, N), the following 2 lines are given in order:
- The first line contains the number of research themes M_i that laboratory i is working on.
- The second line contains the M_i strings W_{i,1}, W_{i,2}, \ldots, W_{i,M_i} representing the research themes of laboratory i, separated by spaces.
Output
Output the number of pairs of laboratories that are "eligible for collaboration" in a single line.
Sample Input 1
3 2 3 ai ml data 4 ml data web security 2 ai ml
Sample Output 1
2
Sample Input 2
4 1 3 biology chemistry physics 2 chemistry medicine 4 physics math statistics chemistry 3 biology ecology environment
Sample Output 2
4
Sample Input 3
5 3 5 deeplearning nlp vision robotics optimization 4 nlp vision speech recognition 6 deeplearning nlp vision gan transformer diffusion 3 robotics control automation 5 nlp vision deeplearning bert attention
Sample Output 3
3