Tudor likes pusheens!
Pusheen Boi has recently requested for a
/pusheen command to be added in Slack, so that he can spam Slack with
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.
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 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.
2 1 1 2 1 2