Основой любой социальной сети является отношение дружбы между двумя пользователями в том или ином смысле. В одной известной социальной сети дружба симметрична, то есть если a является другом b, то b также является другом a. 

В этой же сети есть функция, которая демонстрирует множество людей, имеющих высокую вероятность быть знакомыми для пользователя. Эта функция работает следующим образом. Зафиксируем пользователя x. Пусть некоторый другой человек y, не являющийся другом x на текущий момент, является другом не менее, чем для k% друзей x. Тогда он является предполагаемым другом для x.

У каждого человека в социальной сети есть свой уникальный идентификатор — это целое число от 1 до 10^9. Вам дан список пар пользователей, являющихся друзьями. Определите для каждого упомянутого пользователя множество его предполагаемых друзей.


-----Входные данные-----

В первой строке следуют два целых числа m и k (1 ≤ m ≤ 100, 0 ≤ k ≤ 100) — количество пар друзей и необходимый процент общих друзей для того, чтобы считаться предполагаемым другом.

В последующих m строках записано по два числа a_{i}, b_{i} (1 ≤ a_{i}, b_{i} ≤ 10^9, a_{i} ≠ b_{i}), обозначающих идентификаторы пользователей, являющихся друзьями. 

Гарантируется, что каждая пара людей фигурирует в списке не более одного раза.


-----Выходные данные-----

Для всех упомянутых людей в порядке возрастания id выведите информацию о предполагаемых друзьях. Информация должна иметь вид "id:  k id_1 id_2 ... id_{k}", где id — это id самого человека, k — количество его предполагаемых друзей, а id_1, id_2, ..., id_{k} — идентификаторы его предполагаемых друзей в возрастающем порядке. 


-----Примеры-----
Входные данные
5 51
10 23
23 42
39 42
10 39
39 58

Выходные данные
10: 1 42
23: 1 39
39: 1 23
42: 1 10
58: 2 10 42

Входные данные
5 100
1 2
1 3
1 4
2 3
2 4

Выходные данные
1: 0
2: 0
3: 1 4
4: 1 3

Difficulty: interview

Starter code:

Solutions:
m, k = [int(x) for x in input().split()]

seen = 0
users = set()
friendsof = {}
for i in range(m):
	a, b = [int(x) for x in input().split()]
	users.add(a)
	users.add(b)
	if a in friendsof:
		friendsof[a].add(b)
	else:
		friendsof[a] = set((b,))
	if b in friendsof:
		friendsof[b].add(a)
	else:
		friendsof[b] = set((a,))

users_sorted = list(users)
users_sorted.sort()

for u in users_sorted:
	possible = []
	this_friends = friendsof[u]
	
	for v in users_sorted:
		if v in this_friends: continue
		if v == u: continue
		common = friendsof[v].intersection(this_friends)
		
		if len(common) * 100 >= k * len(this_friends):
			possible.append(v)
	
	print('{}:'.format(u), len(possible), *possible)

def main():
    from collections import defaultdict
    
    m, k = [int(i) for i in input().split()]
    
    d = defaultdict(set)
    for i in range(m):
        a, b = [int(i) for i in input().split()]
        d[a].add(b)
        d[b].add(a)
    
    keys = sorted(d.keys())
    for i in keys:
        result = []
        for j in keys:
            if j not in d[i] and i != j and len(d[i] & d[j]) * 100 >= len(d[i]) * k:
                result.append(j)
        print("{0}: {1} {2}".format(i, len(result), ' '.join(str(i) for i in result)))
            
    
main()


#!/usr/bin/env python
# coding: utf-8

import collections


friends = collections.defaultdict(set)

m, k = list(map(int, input().split()))

for _ in range(m):
    a, b = list(map(int, input().split()))
    friends[a].add(b)
    friends[b].add(a)


for a in sorted(friends):
    a_friends = friends[a]
    probable_friends = []
    for b in friends:
        if a == b or b in a_friends:
            continue
        common_friends = a_friends & friends[b]
        if 100 * len(common_friends) // len(a_friends) >= k:
            probable_friends.append(b)
    print("%d:" % a, len(probable_friends), " ".join(map(str, sorted(probable_friends))))


import sys
from collections import defaultdict

m, k = list(map(int, sys.stdin.readline().split()))
f = defaultdict(list)
for i in range(m):
    a, b = list(map(int, sys.stdin.readline().split()))
    f[a].append(b)
    f[b].append(a)

for i, list_a in sorted(f.items()):
    all_f = set(list_a)
    total_f = len(all_f)
    sugg = []
    for j, list_b in list(f.items()):
        if j == i or j in all_f:
            continue
        common_f = set()
        for p in list_b:
            if p in all_f:
                common_f.add(p)
        if len(common_f) * 100 >= k * total_f:
            sugg.append(j)
    sys.stdout.write('%d: %d %s\n' % (
        i,
        len(sugg),
        ' '.join(map(str, sorted(sugg)))
    ))


from collections import defaultdict
m, k = (int(x) for x in input().split())
friends = defaultdict(set)
maybe = dict()
for i in range(m):
	a, b = (int(x) for x in input().split())
	friends[a].add(b)
	friends[b].add(a)
	maybe[a] = []
	maybe[b] = []
for user1 in friends:
	for user2 in friends:
		if user1 == user2:
			continue
		if user2 in friends[user1]:
			continue
		if len(friends[user1] & friends[user2]) * 100 >= k * len(friends[user1]):
			maybe[user1].append(user2)
for k, v in sorted(maybe.items()):
	print(str(k) + ':', len(v), ' '.join(str(x) for x in sorted(v)))


m, k = map(int, input().split())
fr = []
ppl = set()
for i in range(m):
	a, b = map(int, input().split())
	fr.append((a, b))
	ppl.add(a)
	ppl.add(b)
pairs = {}
for i in ppl:
	pairs[i] = set()
for i in fr:
	pairs[i[0]].add(i[1])
	pairs[i[1]].add(i[0])
# print (pairs)
for i in sorted(ppl):
	tmp = []
	pi = pairs[i]
	qwe = len(pi) * k
	for j in ppl:
		if j in pi or i == j:
			continue
		if len(pi.intersection(pairs[j])) * 100 >= qwe:
			tmp.append(j)
	print("%d: %d %s" % (i, len(tmp), ' '.join(map(str, sorted(tmp)))))

from collections import defaultdict

m, k = map(int, input().split())
friendship = defaultdict(set)
for i in range(m):
    a, b = map(int, input().split())
    friendship[a].add(b)
    friendship[b].add(a)

result = { }
for x, friends in friendship.items():
    s = set()
    for y in friendship:
        if x != y and not y in friends:
            count = 0
            for z in filter(lambda f: y in friendship[f], friends):
                count += 100.0
            if count / len(friends) >= k:
                s.add(y)
    result[x] = s

for x, friends in sorted(result.items()):
    print(x, len(friends), end=' ', sep=": ")
    print(' '.join(map(str, sorted(friends))))


#fin = open("input.txt", "r")
#fout = open("output.txt", "w")

m, k = map(int, input().split())
#print('noshit')
g = dict()
for edge_i in range(m):
	a, b = map(int, input().split())
	if a not in g:
		g[a] = set()
	if b not in g:
		g[b] = set()
	g[a].add(b)
	g[b].add(a)

for x in sorted(g.keys()):
	prob = []
	friends = g[x]
	#print(friends)
	for y in g:
		if y in friends or y == x:
			continue
		#print(y, g[y])
		inter = g[y] & friends
		if len(inter) * 100 >= k * len(friends):
			prob.append(y)
	print(x, ": ", len(prob), end=' ', sep='')
	for elem in sorted(prob):
		print(elem, end=' ')
	print()


n, K = list(map(int, input().split(" ")))
#n, K = map(int, f.readline().split())
azaza = {}
all = set()

for i in range(n):
    a, b = list(map(int, input().split(" ")))
    #a, b = map(int, f.readline().split())

    if a not in azaza:
        azaza[a] = []
    if b not in azaza:
        azaza[b] = []

    azaza[a].append(b)
    azaza[b].append(a)

    all.add(a)
    all.add(b)

ans = {}
for i in all:
    ans[i] = []

for i in all:
    for j in all:
        if i != j and j not in azaza[i]:
            lolka = 0
            for k in azaza[i]:
                if j in azaza[k]:
                    lolka = lolka + 1

            if 100 * lolka / len(azaza[i]) >= K:
                ans[i].append(j)

for i in sorted(ans):
    ansstr = str(i) + ": " + str(len(ans[i])) + ' '
    for j in sorted(ans[i]):
        ansstr += str(j) + ' '
    print(ansstr)







m, k = [int(i) for i in input().split()]

d = {}
for i in range(m):
    a, b = [int(i) for i in input().split()]
    if not d.get(a) : d[a] = []
    if not d.get(b) : d[b] = []
    d[a].append(b)
    d[b].append(a)

mbfriends = {}

for i in d.keys():
    if not mbfriends.get(i) : mbfriends[i] = []
    myk = len(d[i]) * k / 100
    for j in d.keys():
        if i != j and j not in d[i]:
            if len(list(set(d[i]) & set(d[j]))) >= myk:
                mbfriends[i].append(j)

for i in sorted(d.keys()):
    print(str(i) + ":", len(mbfriends[i]), end=" ")
    for j in sorted(mbfriends[i]):
        print(j, end=" ")
    print()



m, k = map(int, input().split())
a = list()
s = set()
for i in range(m):
	c = list(map(int, input().split()))
	a.append(c)
	s.add(c[0])
	s.add(c[1])
d = dict()
for i in s:
	d[i] = set()
for i in a:
	d[i[0]].add(i[1])
	d[i[1]].add(i[0])

tmp = list()
sor = list(s)
sor.sort()
for i in sor:
	tmp = list()
	for j in sor:
		if (i != j) & (j not in d[i]):
			m = d[i] & d[j]
#			print(i, j, d[i] & d[j])
			if (len(m) / len(d[i])) - (k / 100.0) > -0.000000001:
				tmp.append(j)
	print(i, ": ", len(tmp), " ", " ".join(map(str, tmp)), sep = "")


m, k1 = map(int, input().split())
d = dict()
s = set()


for i in range(m):
    a, b = map(int, input().split())
    s.add(a)
    s.add(b)
    if a in d:
        d[a].add(b)
    else:
        d[a] = set()
        d[a].add(b)
        
    if b in d:
        d[b].add(a)
    else:
        d[b] = set()
        d[b].add(a)
ar = []
for i in s:
    ar.append(i)
ar = list(sorted(ar))
for i in ar:
    print(str(i)+": ", end = '')
    sumfr = 0
    arfr = []
    for j in ar:
        if j != i and not(j in d[i]):
            sum1 = 0
            sumall = 0            
            for k in d[i]:
                if j in d[k] and j != k:
                    sum1 += 1
            pr = sum1 / len(d[i]) * 100
            
            if pr >= k1 - 0.000001:
                sumfr += 1
                arfr.append(j)
            
    print(sumfr, end = ' ')
    for i in arfr:
        print(i, end = ' ')
    print()

import sys
from math import ceil,floor

def main():
    n,k = [int(i) for i in input().split()]
    cf = {}
    pf = {}
    for i in range(n):
        pers1,pers2 = [int(i) for i in input().split()]
        if cf.get(pers1) == None:
            cf[pers1] = set()
            pf[pers1] = set()
        cf[pers1].add(pers2)
        if cf.get(pers2) == None:
            cf[pers2] = set()
            pf[pers2] = set()
        cf[pers2].add(pers1)
    persons = list(cf.keys())
    z = len(persons)
    for i in range(z):
        for j in range(0,z):
            pers1 = persons[i]
            pers2 = persons[j]
            if pers1 != pers2 and pers2 not in cf[pers1]:
                m = 0
                for pers3 in cf[pers1]:
                    if pers2 in cf[pers3]:
                        m += 1
                y = (100*m/len(cf[pers1]))
                if y >= k:
                    pf[pers1].add(pers2)
    persons = sorted(persons)
    for pers in persons:
        print(pers,end='')
        print(':',end=' ')
        print(len(pf[pers]),end= ' ')
        ids =  sorted(list(pf[pers]))
        for id in ids:
            print(id,end=' ')
        print()
def __starting_point():
    ##sys.stdin = open("in.txt",'r') 
    ##sys.stdout = open("out.txt",'w')
    main()
    ##sys.stdin.close()
    ##sys.stdout.close()
__starting_point()

from collections import defaultdict

m, k = map(int, input().split())
friendship = defaultdict(set)
for i in range(m):
    a, b = map(int, input().split())
    friendship[a].add(b)
    friendship[b].add(a)

result = { }
for x, friends in friendship.items():
    s = set()
    for y in friendship:
        if x != y and not y in friends:
            count = 0
            for z in filter(lambda f: y in friendship[f], friends):
                count += 100.0
            if count / len(friends) >= k:
                s.add(y)
    result[x] = s

for x, friends in sorted(result.items()):
    print(x, len(friends), end=' ', sep=": ")
    print(' '.join(map(str, sorted(friends))))

m, k = list(map(int, input().split()))

idd = set()
friends = dict()

for i in range(m):
    f, s = list(map(int, input().split()))
    idd.add(f)
    idd.add(s)
    if f not in list(friends.keys()):
        friends[f] = set()
    if s not in list(friends.keys()):
        friends[s] = set()
    friends[f].add(s)
    friends[s].add(f)

people = list(idd)
people.sort()
ans = dict()
for i in range(len(people)):
    ans[people[i]] = []

for i in range(len(people)):
    for j in range(len(people)):
        if i == j:
            continue
        if people[j] in friends[people[i]]:
            continue
        common = 0
        for fr in friends[people[j]]:
            if fr in friends[people[i]]:
                common += 1
        if common * 100 >= k * len(friends[people[i]]):
            ans[people[i]].append(people[j])

for i in range(len(people)):
    print(str(people[i])+ ": " + str(len(ans[people[i]])) + " " + " ".join(list(map(str, ans[people[i]]))))
            


m, p = map(int, input().split())
fr = set()
arr = {}
for i in range(m):
    x, y = map(int, input().split())
    if x in arr:
        arr[x].append(y)
    else:
        arr[x] = [y]
    x, y = y, x
    if x in arr:
        arr[x].append(y)
    else:
        arr[x] = [y]
    fr.add((x, y))
    fr.add((y, x))
res = {}
for x, y in fr:
    res[x] = []
    res[y] = []
for i in arr:
    for j in arr:
        if i == j or (i, j) in fr:
            continue
        r = 0
        for k in arr:
            if i == k or j == k or (i, k) not in fr or (j, k) not in fr:
                continue
            r += 1
        if r * 100 >= p * len(arr[i]):
            res[i].append(j)
m = 0
for k in range(len(res)):
    i = 2 * 10 ** 9
    for j in res:
        if j > m and j < i:
            i = j
    m = i
    print(i, end = ': ')
    print(len(res[i]), end = ' ')
    res[i].sort()
    for j in res[i]:
        print(j, end = ' ')
    print()

from collections import defaultdict
import sys                                                                                                           
#sys.stdin = open('inp.txt', 'r')                                                                                    
                                                                                                                     
m, k = map(int, input().split())
a, a2 = defaultdict(list), defaultdict(list)
for i in range(m):
    x, y = map(int, input().split())
    a[x].append(y)
    a[y].append(x)
for x in a:
    for y in a:
        tmp = 0
        if x != y and y not in a[x]:
            tmp += len(set(a[x]) & set(a[y]))
            if tmp / (len(a[x]) / 100.0) >= k:
                a2[x].append(y)
ans = []
for x in a:
    if x in a2:
        ans += [[x, sorted([y for y in a2[x]])]]
    else:
        ans += [[x, []]]
ans.sort()
for x in ans:
    print(str(x[0]) + ':', len(x[1]), ' '.join(str(z) for z in (y for y in x[1])))

m, p = map(int, input().split())
fr = set()
arr = {}
for i in range(m):
    x, y = map(int, input().split())
    if x in arr:
        arr[x].append(y)
    else:
        arr[x] = [y]
    x, y = y, x
    if x in arr:
        arr[x].append(y)
    else:
        arr[x] = [y]
    fr.add((x, y))
    fr.add((y, x))
res = {}
for x, y in fr:
    res[x] = []
    res[y] = []
for i in arr:
    for j in arr:
        if i == j or (i, j) in fr:
            continue
        r = 0
        for k in arr:
            if i == k or j == k or (i, k) not in fr or (j, k) not in fr:
                continue
            r += 1
        if r * 100 >= p * len(arr[i]):
            res[i].append(j)
m = 0
for k in range(len(res)):#
    i = 2 * 10 ** 9
    for j in res:
        if j > m and j < i:
            i = j
    m = i
    print(i, end = ': ')
    print(len(res[i]), end = ' ')
    res[i].sort()
    for j in res[i]:
        print(j, end = ' ')
    print()

d={}
m,k=map(int,input().split())
for i in range(m):
  a,b=map(int,input().split())
  d.setdefault(a,set()).add(b)
  d.setdefault(b,set()).add(a)
for x in sorted(d):
  s=[]
  for y in sorted(d):
    if x==y or y in d[x]: continue
    if len(d[x]&d[y])*100>=k*len(d[x]): s+=[str(y)]
  print(str(x)+':',len(s),' '.join(s))

m,k=map(int,input().split())
d={}
for _ in range(m):
    x,y=map(int,input().split())
    d.setdefault(x,set()).add(y)
    d.setdefault(y,set()).add(x)
for x in sorted(d):
    ans=[]
    for y in sorted(d):
        if y in d[x] or y==x: continue
        if len(d[x]&d[y])*100>=k*len(d[x]): ans+=[str(y)]
    print(str(x)+':',len(ans),' '.join(ans))

N, part = list(map(int, input().split())) 

part /= 100 

data = dict() 

for i in range(N): 
    fr1, fr2 = list(map(int, input().split())) 

    if fr1 in data: 
        data[fr1].add(fr2) 
    else: 
        data[fr1] = set() 
        data[fr1].add(fr2) 
 
    if fr2 in data: 
        data[fr2].add(fr1) 
    else: 
        data[fr2] = set() 
        data[fr2].add(fr1) 

answer = [] 

for i in list(data.keys()): 
    res = [] 
    for j in list(data.keys()): 
        if i != j and i not in data[j]: 
            com_fr = data[i] & data[j] 
       #     print(len(data[i]) * part, len(com_fr) / len(data[i])) 
            if part <= len(com_fr) / len(data[i]): 
             #   if len(com_fr) != 0: 
                res.append(j) 
    
    answer.append((i, ": ", len(res), ' ', ' '.join(map(str, sorted(res))))) 

answer.sort(key = lambda x: int(x[0]))

for i in range(len(answer)): 
    print(''.join(map(str, answer[i]))) 


xs = dict()
all = set()

n, k = list(map(int, input().split()))

for i in range(n):
    a, b = list(map(int, input().split()))
    try:
        xs[a].add(b)
    except KeyError:
        xs[a] = {b}
    try:
        xs[b].add(a)
    except KeyError:
        xs[b] = {a}
    all.add(a)
    all.add(b)

ys = dict()

for x in xs:
    n = len(xs[x])
    r = []
    for y in all - xs[x] - {x}:
        h = len(xs[x] & xs[y])
        if 100 * h >= n * k:
            r.append(y)
    ys[x] = r

for y in sorted(list(ys.items()), key=lambda p: p[0]):
    print('{}: {} {}'.format(y[0], len(y[1]), ' '.join(list(map(str, sorted(y[1]))))))



n, k = map(int, input().split())
people = {}
tmp = set()
for i in range(n):
    a, b = map(int, input().split())
    if people.get(a) == None:
        people[a] = []
    if people.get(b) == None:
        people[b] = []
    people[a].append(b)
    people[b].append(a)
    tmp.add(a)
    tmp.add(b)
tmp = sorted(tmp)
for i in tmp:
    ans = []
    print(str(i) + ': ', end = '')
    for j in tmp:
        if i == j or people[i].count(j) != 0:
            continue
        cnt = 0
        for fr in people[j]:
            if people[i].count(fr) != 0:
                cnt += 1
        per = (100 * cnt) / len(people[i])
        if int(per) >= k:
            ans.append(j)
    print(len(ans), end = ' ')
    for q in ans:
        print(q, end = ' ')
    print()


f = lambda: map(int, input().split())
g = lambda x, y: d.setdefault(x, set()).add(y)
d = {}
m, k = f()
for i in range(m):
    a, b = f()
    g(a, b)
    g(b, a)
t = sorted(d)
for a in t:
    s = [str(b) for b in t if a != b and b not in d[a] and len(d[a] & d[b]) * 100 >= k * len(d[a])]
    print(str(a) + ':', len(s), ' '.join(s))

f = lambda: map(int, input().split())
g = lambda x, y: d.setdefault(x, set()).add(y)
h = lambda b: a == b or b in d[a] or len(d[a] & d[b]) * 100 < k * len(d[a])
d = {}
m, k = f()
for i in range(m):
    a, b = f()
    g(a, b)
    g(b, a)
t = sorted(d)
for a in t:
    s = [str(b) for b in t if not h(b)]
    print(str(a) + ':', len(s), ' '.join(s))