← 返回题目列表

Codeforces · 524/A

A. 也许你认识这些人?

中文机器翻译题面 查看原题

任何社交网络的基础都是两个用户之间某种意义上的友谊关系。 In one well-known social network, friendship is symmetrical, that is, if a is a friend of b, then b is also a friend of a.

The same network has a function that shows a lot of people who have a high probability of being familiar to the user.该函数的工作原理如下。让我们修复用户 x。 Let some other person y, who is not a friend of x at the current moment, be a friend of at least k% of x's friends.那么他就是 x 的推定朋友。

社交网络上的每个人都有自己的唯一标识符 - 这是一个从 1 到 109 的整数。您会得到一个好友用户对的列表。对于每个提到的用户,确定他假定的朋友集。

输入

第一行包含两个整数 m 和 k (1 ≤ m ≤ 100, 0 ≤ k ≤ 100) — 朋友对的数量以及被视为假定朋友所需的共同朋友百分比。

The next m lines contain two numbers ai, bi (1 ≤ ai, bi ≤ 109, ai ≠ bi), denoting the identifiers of users who are friends.

保证每对人最多在列表中出现一次。

输出

For all mentioned people, in ascending order by id, print information about supposed friends.该信息的格式应为“id: k id1 id2...idk”,其中 id 是该人自己的 id,k 是他假定的朋友的数量,id1、id2、...、idk 是他假定的朋友的标识符(按升序排列)。

示例

输入 #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