#P2247. SAC#1 - ACOJ云评测计划

SAC#1 - ACOJ云评测计划

题目背景

本题由世界上最蒟蒻最辣鸡最撒比的 SOL 提供。

寂月城网站是完美信息教室的官网。地址:http://191.101.11.174/mgzd

题目描述

ACOJ 的服务器简直是差到了一个令人发指的地步。于是 SAC 的出题人,也就是傻逼 SOL,不得不强制要求每一个通过下载 ACOJ 软件包而搭建的分站,都为主站启动云端评测服务。

云评测服务是由网络来连接的。这样的网络连接是双向的;但是由于地理位置等因素的限制,并不是任意两台服务器都可以直接相连。ACOJ 主站已经得到了可以直连的服务器的表,其中包含 nn 个分站(包括主站)以及它们的 mm 条连接情况,可以根据这个来分配各个分站的任务。

有一些分站的服主是 SOL 的脑残粉。他们会无条件地将他们的服务器提供给 SOL。这些 ACOJ 分站称作“好站”。但是还有一些分站的服主是 SOL 黑。他们虽然拿到了 ACOJ 的服务端,但是并不愿意为 SOL 提供资源,于是利用黑科技关掉了云服务。也就是说,虽然主站仍然认为这些站点存在,但是它们不会起到任何作用——既不能传递通信,也不能进行评测。它们称作“坏站”。

经过千辛万苦的调查,SOL 确定了 ACOJ 云评测系统中有最多 kk 个坏站存在,而且这 kk 个坏站似乎会使得 ACOJ 的云网络不再联通!大危机!

但是 SOL 太弱智了,并不能确定是哪 kk 个。于是他请你来帮他找出任意一组可能会使得网络不再联通的 kk 个站点,以便加强防范。

输入格式

输入包含 m+1m+1 行。

1133 个整数 n,m,kn,m,k

接下来 mm 行,每行两个整数 a,ba,b,表示标号为 aabb 的站点可以直接相连。

输出格式

输出包含 11 行。

不超过 kk 个整数,表示能够将原图割开的任意一组节点组合。

因为使用了 Special Judge,所以节点的顺序并不用担心。只需要满足能够割开原图即可。

如果不存在这样的站点集合,输出 How oversuspicious you are, SOL!;如果网络不存在任何坏站时本来就无法连通,输出 Poor SOL!

4 4 2
1 2
2 3
3 4
4 1
1 3
4 6 2
1 2
2 3
3 4
4 1
1 3
2 4 
How oversuspicious you are, SOL!
4 0 2
Poor SOL!

提示

对于 20%20\% 的数据,n15n \le 15

对于另外 20%20\% 的数据,n100n \le 100k=1k=1

对于另外 20%20\% 的数据,n100n \le 100k=2k=2

对于 100%100\% 的数据,3n5003 \le n\le 500k3k \le 32nk2\le n - k,云网络不存在自环和重边。