10209_Telecowmunication

Farmer John's cows like to keep in touch via email so they have created a network of cowputers so that they can intercowmunicate. These machines route email so that if there exists a sequence of c cowputers a₁, a₂, ..., a_c such that a₁ is connected to a₂, a₂ is connected to a₃, and so on then a₁ and a_c can send email to one another.

Unfortunately, a cow will occasionally step on a cowputer or Farmer John will drive over it, and the machine will stop working. This means that the cowputer can no longer route email, so connections to and from that cowputer are no longer usable.

Two cows are pondering the minimum number of these accidents that can occur before they can no longer use their two favorite cowputers to send email to each other. Write a program to calculate this minimal value for them, and to calculate a set of machines that corresponds to this minimum.

For example the network:

1*
/   
3 - 2*

shows 3 cowputers connected with 2 lines. We want to send messages between 1 with 2. Direct lines connect 1-3 and 2-3. If cowputer 3 is down, them there is no way to get a message from 1 to 2.

Multiple test cases. For each case:

Line 1 :  Four space-separated integers: N, M, c₁, and c₂. N is the number of computers (1 ≤ N ≤ 100), which are numbered 1..N. M is the number of connections between pairs of cowputers (1 ≤ M ≤ 600). The last two numbers, c₁ and c₂, are the id numbers of the cowputers that the questioning cows are using. Each connection is unique and bidirectional (if c₁ is connected to c₂, then c₂ is connected to c₁). There can be at most one wire between any two given cowputers. Computer c₁ and c₂ will not have a direction connection.

Lines 2..M+1 :   The subsequent M lines contain pairs of cowputers id numbers that have connections between them.

For each case, output two lines :

The first line is the minimum number of cowputers that can be down before terminals c₁ & c₂ are no longer connected. The second line is a minimal-length sorted list of cowputers that will cause c₁ & c₂ to no longer be connected.

Note that neither c₁ nor c₂ can go down. In case of ties, the program should output the set of computers that, if interpreted as a base N number, is the smallest one.

3 2 1 2
1 3
2 3

1
3