Problem: On the Internet shopping site, on the same page as the product that the user is currently viewing, some other products that other users have bought in the past along with the product that they are currently viewing are displayed. It is believed that sales can be increased by presenting products that are considered to be highly relevant.

Similar things can be seen in local supermarkets (such as bread and jam) as a way to place items that are often bought together nearby. Your job is to write a program that will help you devise product placement. This time, I would like to set a certain standard number of times and find a combination of two products for which the number of times bought together is equal to or greater than the standard number of times.

When given the information of the products bought together and the standard number of times, create a program that outputs the combination of the two products bought together more than the standard number of times.



Input

The input is given in the following format.


N F
info1
info2
::
infoN


The first line gives the number of pieces of information N (1 ≤ N ≤ 100) and the reference number F (1 ≤ F ≤ 100) of the items bought together. The following N lines are given information on the products bought together. Information about the products bought together infoi is given in the following format.


M item1 item2 ... itemM


M (1 ≤ M ≤ 10) indicates how many products this information contains. itemj is the name of the item bought in this purchase and is a string of 1 to 30 length consisting of only lowercase letters. The same product is never given in infoi.

Output

The number of combinations of two products bought together more than the reference number of times is output on the first line, and all combinations are output on the second and subsequent lines. However, if there is no combination, nothing is output after the second line.

The output order is as follows after arranging the product names in the combination in the lexicographic order (the order in which the words are arranged in the English-Japanese dictionary).

* Compare the first product names, and the one with the earliest in lexicographic order comes first.
* If they are the same, compare the second product names and the lexicographic order comes first.



Separate product names with a single space, and separate product combinations with a single line break.

Examples

Input

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


Output

3
bread milk
bread potato
cornflakes milk


Input

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


Output

0

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;

const int MINS = -2000;

typedef pair<string, string> P;

map<string, int > id;
string str[1005];
vector<int> vec[1005];
vector<string> data[105];
int flag[1005][1005]={};
vector<P> output;

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int n,f;
  cin >> n >> f;
  
  int index = 1;
  for(int i=0;i<n;i++){
    int m;
    cin >> m;
    for(int j=0;j<m;j++){
      string s;
      
      cin >> s;
      data[i].push_back(s);
      if(id[s] == 0){
	id[s] = index;
	str[ id[s] ] = s;
	++index;
      }
    }
    
    for(int k=0;k<data[i].size();k++){
      string s;
      int idx;
      s = data[i][k];
      idx = id[s];
      for(int l=0;l<m;l++){
	if(s == data[i][l]) continue;
	vec[idx].push_back( id[ data[i][l] ] );
      }
    }
  }
  
  /*
  for(int i=1;i<index;i++){
    cout << i << " = "; 
    for(int j=0;j<vec[i].size();j++){
      cout << vec[i][j] << ' ';
    }
    cout << endl;
  }
  */
  //for(int i=0;i<index;i++) sort(vec, vec+index);

  int ans=0;
  for(int i=1;i<index;i++){
    int count[1005]={};
    for(int j=0;j<vec[i].size();j++){
      int idx = vec[i][j];
      count[idx]++;
      //cout << count[idx] << ' ' << str[idx] << endl;
      if(count[idx] >= f && flag[i][idx] == 0) {
	if(str[i] < str[idx]){
	  output.push_back(P(str[i], str[idx]));
	} else {
	  output.push_back(P(str[idx], str[i]));
	}
	ans++;
	count[idx] = MINS;
	flag[i][idx] = flag[idx][i] = 1;
	
      }
    }
  }

  cout << ans << endl;
  sort(output.begin(), output.end());
  for(int i=0;i<ans;i++){
    cout << output[i].first << ' ' << output[i].second << endl;
  }

  

  return 0;
}