#USACO1545. 奶牛通信

奶牛通信

农夫约翰的奶牛喜欢通过电子邮件保持联系,因此它们建立了一个奶牛电脑网络,以便彼此交流。

它们以如下方式进行邮件互通:假设有 cc 台电脑 a1,a2,..,aca_1,a_2,..,a_c其中 a1a_1 连接 a2a_2a2a_2 连接 a3a_3,以此类推,那么 a1a_1aca_c 之间就可以相互收发邮件。

不幸的是,有时一些电脑会发生故障,而坏掉的电脑是不能做到信息传递的,那么与这台电脑相关的连接也就不能使用了。

现在,有两头奶牛正在考虑,如果要使它们之间的联系中断,至少要坏掉多少台电脑,这些电脑是哪几台?

不考虑这两头奶牛的电脑坏掉的情况。

例如,考虑如下网络:

                1
              /  
             3 - 2

如果要让 1122 之间的联系中断,则让 33 号电脑坏掉即可。

输入格式

第一行包含四个整数 𝑁,𝑀,𝑐1,𝑐2𝑁,𝑀,𝑐_1,𝑐_2,表示共有 𝑁𝑁 台电脑(编号 1𝑁1∼𝑁),其中存在 𝑀𝑀 条连接,每条连接将两台电脑直接相连。我们需要考虑的两头奶牛的电脑的编号分别为 c1,c2c_1,c_2

每个连接都是唯一的且是双向的,任意两台电脑之间最多存在一条连接,c1c_1c2c_2 之间没有直接连接。

接下来 MM 行,每行包含两个整数 x,yx,y,表示电脑 xx 与电脑 yy 之间存在一条连接。

输出格式

第一行输出一个整数 𝐿𝐿,表示至少要坏掉的电脑的数量。

第二行按升序输出 𝐿𝐿 个整数,表示所有要坏掉的电脑的编号。

如果答案不唯一,则将答案视为一个 𝐿𝐿 位的 𝑁𝑁 进制数字,输出该数字最小的答案。

3 2 1 2
1 3
2 3
1
3

提示

1𝑁100,1≤𝑁≤100,

1𝑀600,1≤𝑀≤600,

1𝑐1,𝑐2,𝑥,𝑦𝑁1≤𝑐_1,𝑐_2,𝑥,𝑦≤𝑁