#P2247. SAC#1 - ACOJ云评测计划
SAC#1 - ACOJ云评测计划
题目背景
本题由世界上最蒟蒻最辣鸡最撒比的SOL提供。
寂月城网站是完美信息教室的官网。地址:http://191.101.11.174/mgzd 。
题目描述
ACOJ的服务器简直是差到了一个令人发指的地步。于是SAC的出题人,也就是傻逼SOL,不得不强制要求每一个通过下载ACOJ软件包而搭建的分站,都为主站启动云端评测服务。
云评测服务是由网络来连接的。这样的网络连接是双向的;但是由于地理位置等因素的限制,并不是任意两台服务器都可以直接相连。ACOJ主站已经得到了可以直连的服务器的表,其中包含n个分站(包括主站)以及它们的m条连接情况,可以根据这个来分配各个分站的任务。
有一些分站的服主是SOL的脑残粉。他们会无条件地将他们的服务器提供给SOL。这些ACOJ分站称作“好站”。但是还有一些分站的服主是SOL黑。他们虽然拿到了ACOJ的服务端,但是并不愿意为SOL提供资源,于是利用黑科技关掉了云服务。也就是说,虽然主站仍然认为这些站点存在,但是它们不会起到任何作用——既不能传递通信,也不能进行评测。它们称作“坏站”。
经过千辛万苦的调查,SOL确定了ACOJ云评测系统中有最多k个坏站存在,而且这k个坏站似乎会使得ACOJ的云网络不再联通!大危机!
但是SOL太弱智了,并不能确定是哪k个。于是他请你来帮他找出任意一组可能会使得网络不再联通的k个站点,以便加强防范。
输入格式
输入包含m+1行。
第1行3个整数n、m、k。
接下来m行,每行两个整数a、b,表示标号为a和b的站点可以直接相连。
输出格式
输出包含1行。
不超过k个整数,表示能够将原图割开的任意一组节点组合。
因为使用了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%的数据,n <= 15。
对于另外20%的数据,n <= 100,k=1。
对于另外20%的数据,n <= 100,k=2。
对于100%的数据,3 <= n <= 500,k <= 3,n-k >= 2,云网络不存在自环和重边。