Возможно, вы знаете этих людей?

题意翻译

### 题目描述 从某种意义上来说，任何社交网络的基础是在两个人之间的朋友关系。在一个已知的社交网络中，友谊是相互的，意思是，如果$ 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} $是他可能的朋友的标识码，请按递增的顺序输出。 Translated by zhouyonglong

题目背景

Perhaps you know these people? 也许你也认识这些人？

题目描述

Основой любой социальной сети является отношение дружбы между двумя пользователями в том или ином смысле. В одной известной социальной сети дружба симметрична, то есть если $ 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} $ — идентификаторы его предполагаемых друзей в возрастающем порядке.

输入输出样例

输入样例 #1

5 51
10 23
23 42
39 42
10 39
39 58

输出样例 #1

10: 1 42
23: 1 39
39: 1 23
42: 1 10
58: 2 10 42

输入样例 #2

5 100
1 2
1 3
1 4
2 3
2 4

输出样例 #2

1: 0
2: 0
3: 1 4
4: 1 3

题意翻译

### 题目描述 从某种意义上来说，任何社交网络的基础是在两个人之间的朋友关系。在一个已知的社交网络中，友谊是相互的，意思是，如果$ 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} $是他可能的朋友的标识码，请按递增的顺序输出。 Translated by zhouyonglong