Double Doors Regional P3 - Tudor and the Pusheens

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Java 5.0s
Memory limit: 256M
Java 256M

Problem type

Tudor likes pusheens!

Pusheen Boi has recently requested for a /pusheen command to be added in Slack, so that he can spam Slack with pusheens.

Meanwhile, Tudor's farm of N servers has gotten to be rather large. There are M pairs of servers that are connected and therefore can directly communicate with each other. A server can vacuously communicate with itself. All servers can communicate with each other, perhaps by using intermediate servers.

Pusheen Boi wants to make sure that he can send pusheens from server S to server T. Tudor, wanting to reduce the complexity of his server farm, wants to know the maximum number of pairs of servers that he can disconnect while still preserving Pusheen Boi's wishes.

Input Specification

The input starts with two integers N and M, (1 \le N, M \le 10^6).

M pairs of lines follow, each containing two distinct integers X and Y, indicating that servers X and Y can communicate. You may assume (1 \le X < Y \le N) and no edges appears more than once.

The final line of input contains two integers, S and T.

Output Specification

Output the maximum number of pairs of servers that can be disconnected, such that S and T can still communicate.

Sample Data ZIP

Click here for ZIP.

Sample Input

2 1
1 2
1 2

Sample Output