#USACO1545. 奶牛通信
奶牛通信
农夫约翰的奶牛喜欢通过电子邮件保持联系,因此它们建立了一个奶牛电脑网络,以便彼此交流。
它们以如下方式进行邮件互通:假设有 台电脑 其中 连接 , 连接 ,以此类推,那么 与 之间就可以相互收发邮件。
不幸的是,有时一些电脑会发生故障,而坏掉的电脑是不能做到信息传递的,那么与这台电脑相关的连接也就不能使用了。
现在,有两头奶牛正在考虑,如果要使它们之间的联系中断,至少要坏掉多少台电脑,这些电脑是哪几台?
不考虑这两头奶牛的电脑坏掉的情况。
例如,考虑如下网络:
1
/
3 - 2
如果要让 和 之间的联系中断,则让 号电脑坏掉即可。
输入格式
第一行包含四个整数 ,表示共有 台电脑(编号 ),其中存在 条连接,每条连接将两台电脑直接相连。我们需要考虑的两头奶牛的电脑的编号分别为 。
每个连接都是唯一的且是双向的,任意两台电脑之间最多存在一条连接, 和 之间没有直接连接。
接下来 行,每行包含两个整数 ,表示电脑 与电脑 之间存在一条连接。
输出格式
第一行输出一个整数 ,表示至少要坏掉的电脑的数量。
第二行按升序输出 个整数,表示所有要坏掉的电脑的编号。
如果答案不唯一,则将答案视为一个 位的 进制数字,输出该数字最小的答案。
3 2 1 2
1 3
2 3
1
3
提示