A9810. Возможно, вы знаете этих людей?
编程题
普及/提高-
知识点
题目描述
Perhaps you know these people?
也许你也认识这些人？
也许你也认识这些人？
输入格式
Основой любой социальной сети является отношение дружбы между двумя пользователями в том или ином смысле. В одной известной социальной сети дружба симметрична, то есть если $a$ является другом $b$ , то $b$ также является другом $a$ .
В этой же сети есть функция, которая демонстрирует множество людей, имеющих высокую вероятность быть знакомыми для пользователя. Эта функция работает следующим образом. Зафиксируем пользователя $x$ . Пусть некоторый другой человек $y$ , не являющийся другом $x$ на текущий момент, является другом не менее, чем для $k\%$ друзей $x$ . Тогда он является предполагаемым другом для $x$ .
У каждого человека в социальной сети есть свой уникальный идентификатор — это целое число от $1$ до $10^{9}$ . Вам дан список пар пользователей, являющихся друзьями. Определите для каждого упомянутого пользователя множество его предполагаемых друзей.
В этой же сети есть функция, которая демонстрирует множество людей, имеющих высокую вероятность быть знакомыми для пользователя. Эта функция работает следующим образом. Зафиксируем пользователя $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}$ ), обозначающих идентификаторы пользователей, являющихся друзьями.
Гарантируется, что каждая пара людей фигурирует в списке не более одного раза.
В последующих $m$ строках записано по два числа $a_{i},b_{i}$ ( $1<=a_{i},b_{i}<=10^{9}$ , $a_{i}≠b_{i}$ ), обозначающих идентификаторы пользователей, являющихся друзьями.
Гарантируется, что каждая пара людей фигурирует в списке не более одного раза.
输入输出样例
输入 #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