任何社交网络的基础都是两个用户之间某种意义上的友谊关系。 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