题目内容

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

平台上有$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$