Related Products

Time Limit : 1 sec, Memory Limit : 262144 KB

関連商品

インターネット通販サイトでは、ユーザが現在見ている商品と同じページに、過去に他のユーザによって、現在見ている商品と一緒に買われた別の商品をいくつか表示してくれます。関連性の高いと思われる商品を提示することで、売り上げを伸ばすことができると考えられているからです。

似たようなことは、一緒に買われることが多い商品を近くに配置する、という工夫として、近所のスーパーマーケットでも目にすることができます(例えば、パンとジャムのような)。あなたの仕事は、商品配置の工夫を助けるプログラムを書くことです。今回は、ある基準となる回数を設定し、一緒に買われた回数が基準回数以上である、2つの商品の組み合わせを求めたいと思います。

一緒に買われた商品の情報と基準回数が与えられたとき、基準回数以上一緒に買われた商品2つの組み合わせを出力するプログラムを作成せよ。

Input

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

N F
info1
info2
:
infoN

1行目に、一緒に買われた商品の情報の数 N (1 ≤ N ≤ 100) と、基準回数 F (1 ≤ F ≤ 100) が与えられる。続く N行に、一緒に買われた商品の情報が与えられる。一緒に買われた商品の情報 infoi は、以下の形式で与えられる。

M item1 item2 ...  itemM

M (1 ≤ M ≤ 10) は、この情報がいくつの商品を含むかを表す。itemj は、この買い物で買われた商品の名前であり、英小文字だけから成る長さ 1 以上 30 以下の文字列である。infoi の中に同じ商品が与えられることはない。

Output

1行目に基準回数以上一緒に買われた商品2つの組み合わせの数を出力し、2行目以降に組み合わせをすべて出力する。ただし、組み合わせが一つもない場合は2行目以降には何も出力しない。

出力の順番は、組み合わせ内の商品名どうしを、辞書式順序(英和辞書で単語が並んでいる順番)で並べたあと、組み合わせどうしについては以下のようにする。

  • 一つ目の商品名どうしを比較して、辞書式順序で早いほうが先。
  • 同じ場合は、二つ目の商品名どうしを比較して、辞書式順序で早いほうが先。

商品名はスペース一つで区切り、商品の組み合わせは改行一つで区切る。

Sample Input 1

5 2
3 bread milk banana
2 milk cornflakes
3 potato bread milk
4 cornflakes bread milk butter
2 potato bread

Sample Output 1

3
bread milk
bread potato
cornflakes milk

Sample Input 2

5 5
3 bread milk banana
2 milk cornflakes
3 potato bread milk
4 cornflakes bread milk butter
2 potato bread

Sample Output 2

0

Source: PC Koshien 2015 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2015-11-7
http://web-ext.u-aizu.ac.jp/pc-concours/