题面描述:

在这个问题中，我们需要为社交网络平台上的用户提供好友推荐功能。具体而言，输入包括用户总数 (N)、好友关系总数 (M)、待推荐用户编号 (K) 以及需要推荐的好友数量 (L)。随后会有 (M) 行数据，表示用户之间的好友关系。我们需根据用户 (K) 的共同好友数量来计算其与其他用户的相似度，推荐相似度最高的 (L) 个用户，且推荐用户不能是用户 (K) 的好友。推荐结果需按相似度从高到低排序，若相似度相同，则按用户编号从小到大排序。如果找到的候选用户少于 (L) 个，则需要补充与用户 (K) 没有任何共同好友的其他用户，如果仍不足 (L) 个，则用 (0) 补位。通过这个推荐功能，可以帮助用户发现新的好友，增强社交网络的互动。

思路：模拟

题目要求给目标用户推荐好友，首先被推荐对象不能是目标用户的好友。因此我们在读入用户关系时，标记一下与目标用户互为好友的用户。

之后，枚举所有未被标记用户，他们都是待定对象。而与目标用户相似度，就是与其相连的边中，被标记的点的数量。因此统计后再排序即可。

题目内容

你正在为一个社交网络平台开发好友推荐功能。

平台上有$N$个用户(每个用户使用$1$到$N$的整数编号)，同时系统中维护了用户之间的好友关系。

为了推荐新朋友，平台决定采用“共同好友数量”作为衡量两个用户之间相似度的标准。

系统根据输入用户编号$K$，输出与此用户$K$相似度最高的前$L$个用户$ID$，来推荐给用户$K$。

相似度定义:两个用户非好友，两个用户的相似度为拥有的共同好友数(例如用户$A$和用户$B$，只有共同好友$C$和$D$，相似度=$2$)

输入描述

第一行包含四个整数$N$，$M$、$K$和$L$，分别表示用户的数量($N$)，好友记录条数($M$)、查询的用户编号($K$)和推荐的好友数量($L$)。

接下来$M$行，每行包含两个整数编号$X$和$Y$，表示编号为$X$和$Y$用户是好友。

1.输入格式都是标准的，无需考虑输出异常场景(不会包含用户和自己是好友的输入,例如$1$ $1$)

2.用户数不超过$1024$，用户编码最大$10244$

3.好友记录数不超过$10240$

输出描述

根据输入$K$和$L$，输出和用户$K$相似度最高的$L$个用户编码。

1.输出相似度最高的前$L$个用户编码，按照相似度从高到低排序

2.如果有相似度相同的可能好友，按照用户编号从小到大排序

3.如果推荐的好友个数不足$L$个，则推荐与用户$K$无无共同好友关系的用户(陌生人)作为可能好友;如果 推荐仍不满足$L$个用户，剩余推荐用户编码使用$0$来占位

样例1

输入

6 7 3 2
1 2
1 3
2 3
3 4
3 5
4 5
5 6

输出

6 0

解释

输入包含了$6$个用户，$7$条好友记录，给用户$ID$编号为$3$的用户推荐$2$个好友

输出只有编号为$6$的用户可能是编号$3$用户的可能好友；

尝试推荐与编号$3$用户无共同好友的其他用户，由于除编号为$6$的用户之外，其他用户和编号$3$用户都是好友，所以找不到陌生人作为推荐的第二个用户；

推荐结果不足$2$个用户，所以推荐的第二个用户编码使用$0$来占位补足。

样例2

输入

8 11 1 3
1 2
1 3
2 3
3 4
3 5
4 5
5 6
6 7
7 8
1 8
2 7

输出

7 4 5

解释

输入包含了$8$个用户，$11$条好友记录，给用户$ID$编号为$1$的用户推荐$3$个好友。

按照相似度排序推荐给用户$1$的相关好友:$7$ $4$ $5$