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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
(N, F) = map(int, input().split())
data = []
tmp = {}
for i in range(N):
	data.append(list(input().split()))
	for x in range(1, len(data[i]) - 1):
		for y in range(x + 1, len(data[i])):
			a = data[i][x]
			b = data[i][y]
			(a, b) = (min(a, b), max(a, b))
			if (a, b) not in tmp:
				tmp[a, b] = 1
			else:
				tmp[a, b] += 1
ans = []
for k in tmp:
	if tmp[k] >= F:
		ans.append(list(k))
ans = sorted(ans, key=lambda x: x[1])
ans = sorted(ans)
print(len(ans))
if len(ans) != 0:
	for i in range(len(ans)):
		print(*ans[i])


(n, f) = map(int, input().split())
a = {}
for _ in range(n):
	(m, *c) = input().split()
	m = int(m)
	for i in range(m - 1):
		for j in range(i + 1, m):
			p = (min(c[i], c[j]), max(c[i], c[j]))
			if p in a:
				a[p] += 1
			else:
				a[p] = 1
b = []
for k in a:
	if a[k] >= f:
		b.append((k, a[k]))
b.sort(key=lambda x: x[0][1])
b.sort(key=lambda x: x[0][0])
print(len(b))
for i in b:
	print(*i[0])


from itertools import combinations
(N, F) = map(int, input().split())
goods = [sorted(g) for _ in range(N) for g in list(combinations(list(map(str, input().split()))[1:], 2))]
sets = set(((g[0], g[1]) for g in goods))
s = [(s[0], s[1]) for s in sets if goods.count([s[0], s[1]]) >= F]
n = [sum((1 for s in sets if goods.count([s[0], s[1]]) >= F))]
for a in n:
	print(a)
else:
	if n[0] != 0:
		for t in sorted(sorted(s, key=lambda x: x[1])):
			print(*t)


def combinations(l):
	sl = sorted(l)
	r = range(len(sl) - 1)
	for i in r:
		for j in range(i + 1, len(sl)):
			yield (sl[i], sl[j])
(m, n) = [int(s) for s in input().split()]
d = {}
for i in range(m):
	l = input().split()[1:]
	for e in combinations(l):
		if e in d:
			d[e] += 1
		else:
			d[e] = 1
sl = sorted([e[0][0] + ' ' + e[0][1] for e in d.items() if e[1] >= n])
print(len(sl))
for i in sl:
	print(i)


import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy
BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
MOD = 1000000007
EPS = 1e-09

class Info:

	def __init__(self, arg_item_A, arg_item_B):
		self.item_A = arg_item_A
		self.item_B = arg_item_B
		if self.item_B < self.item_A:
			(self.item_A, self.item_B) = (self.item_B, self.item_A)

	def __lt__(self, another):
		if self.item_A != another.item_A:
			return self.item_A < another.item_A
		else:
			return self.item_B < another.item_B
SIZE = 1000
(N, F) = map(int, input().split())
num_item = 0
ITEM = {}
rev_ITEM = {}
table = [[0] * SIZE for _ in range(SIZE)]
for _ in range(N):
	(M, *input_str) = map(str, input().split())
	M = int(M)
	for i in range(M):
		if input_str[i] not in ITEM:
			ITEM[input_str[i]] = num_item
			rev_ITEM[num_item] = input_str[i]
			num_item += 1
	for i in range(M - 1):
		for k in range(i + 1, M):
			table[ITEM[input_str[i]]][ITEM[input_str[k]]] += 1
			table[ITEM[input_str[k]]][ITEM[input_str[i]]] += 1
ANS = []
for i in range(num_item - 1):
	for k in range(i + 1, num_item):
		if table[i][k] >= F:
			ANS.append(Info(rev_ITEM[i], rev_ITEM[k]))
print('%d' % len(ANS))
ANS.sort()
for i in range(len(ANS)):
	print('%s %s' % (ANS[i].item_A, ANS[i].item_B))


import sys
l = input().split()
f = int(l[1])
t = {}
for l in sys.stdin:
	e = l.split()
	m = int(e.pop(0))
	s = sorted(e)
	for i in range(m):
		for j in range(i + 1, m):
			k = (s[i], s[j])
			if k in t:
				t[k] += 1
			else:
				t[k] = 1
f = list(sorted(filter(lambda x: t[x] >= f, t)))
print(len(f))
for e in f:
	print('{0:s} {1:s}'.format(e[0], e[1]))


from collections import Counter
counter = Counter()
(n, f) = map(int, input().split())
for _ in range(n):
	items = input().split()
	m = int(items[0])
	items = items[1:]
	items.sort()
	for i in range(m):
		for j in range(i + 1, m):
			counter[items[i], items[j]] += 1
lst = [(k, v) for (k, v) in counter.most_common() if v >= f]
lst.sort()
print(len(lst))
for (k, v) in lst:
	print(*k)


(n, f) = map(int, input().split())
pair = {}
for i in range(n):
	(m, *items) = input().split()
	m = int(m)
	for p in range(m):
		for q in range(p):
			key = tuple(sorted([items[p], items[q]]))
			pair[key] = pair.get(key, 0) + 1
ans = sorted((key for key in pair if pair[key] >= f))
print(len(ans))
if ans:
	for (a, b) in ans:
		print(a, b)


(N, F) = [int(i) for i in input().split()]
itemsets = []
for l in range(N):
	items = input().split()
	M = int(items.pop(0))
	items.sort()
	for i in range(len(items)):
		for j in range(i + 1, len(items)):
			itemsets.append(items[i] + ' ' + items[j])
itemsets.sort()
cnt = 1
ans = []
if F > 1:
	ans.append('')
	for i in range(1, len(itemsets)):
		if itemsets[i] == itemsets[i - 1]:
			cnt = cnt + 1
			if cnt >= F and itemsets[i] != ans[-1]:
				ans.append(itemsets[i])
		else:
			cnt = 1
	ans.pop(0)
else:
	ans = itemsets
print(len(ans))
for i in range(len(ans)):
	print(ans[i])