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

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

У каждого человека в социальной сети есть свой уникальный идентификатор — это целое число от 1 до 10<sup class="upper-index">9</sup>. Вам дан список пар пользователей, являющихся друзьями. Определите для каждого упомянутого пользователя множество его предполагаемых друзей.
В первой строке следуют два целых числа *m* и *k* (1 ≤ *m* ≤ 100, 0 ≤ *k* ≤ 100) — количество пар друзей и необходимый процент общих друзей для того, чтобы считаться предполагаемым другом.

В последующих *m* строках записано по два числа *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>, *a*<sub class="lower-index">*i*</sub> ≠ *b*<sub class="lower-index">*i*</sub>), обозначающих идентификаторы пользователей, являющихся друзьями. 

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

m, k = [int(x) for x in input().split()]
adj_sets = collections.defaultdict(set)

may_know = collections.defaultdict(list)

for i in range(m):
    id1, id2 = [int(x) for x in input().split()]
    adj_sets[id1].add(id2)
    adj_sets[id2].add(id1)
    may_know[id1] = list()
    may_know[id2] = list()

for id1 in adj_sets:
    for id2 in adj_sets:
        if id1 == id2 or id2 in adj_sets[id1]:
            continue
        common_friends = adj_sets[id1].intersection(adj_sets[id2])
        if len(common_friends)/len(adj_sets[id1]) >= k/100:
            may_know[id1].append(id2)


def print_list(i, l):
    sorted(l)
    print(str(i) + ': ' + str(len(l)), end=' ')
    for item in l:
        print(item, end=' ')
    print()

for item in sorted(may_know.items(), key=lambda x: x[0]):
    print_list(item[0], item[1])
