P1345 [USACO5.4] Telecowmunication

Farmer John's cows like to keep in touch by email, so they set up a cow computer network to communicate. The machines send email as follows: if there exists a sequence of $c$ computers $a_1,a_2,\cdots ,a_c$ such that $a_1$ is connected to $a_2$, $a_2$ is connected to $a_3$, and so on, then computers $a_1$ and $a_c$ can exchange email. Unfortunately, sometimes a cow may accidentally step on a computer, and Farmer John's truck might run over a computer, and that unlucky computer will break. This means that computer can no longer send email, and all connections incident to it become unusable. Two cows wonder: if the two of us are to be unable to email each other, what is the minimum number of computers that must fail? Note that $c_1$ and $c_2$ cannot be destroyed. Please write a program to compute this minimum. Consider the following network: ```plain 1* / 3 - 2* ``` This figure shows $3$ computers with $2$ connections. We want to send messages between computers $1$ and $2$. Computer $1$ is directly connected to $3$, and $2$ is directly connected to $3$. If computer $3$ fails, then $1$ and $2$ can no longer communicate.

The first line contains four space-separated integers: $N, M, c_1, c_2$. $N$ is the total number of computers, numbered from $1$ to $N$. $M$ is the total number of connections. The last two integers $c_1$ and $c_2$ are the computers used by the two cows mentioned above. Connections have no duplicates and are undirected (i.e., if $c_1$ is connected to $c_2$, then $c_2$ is connected to $c_1$ as well). There is at most one connection between any pair of computers. Computers $c_1$ and $c_2$ are not directly connected. Lines $2$ to $M+1$: each of the next $M$ lines contains the indices of two directly connected computers.

One line containing a single integer: the minimum number of computers that must fail to make computers $c_1$ and $c_2$ unable to communicate with each other.

For $100\%$ of the testdata: $1 \le N \le 100$, $1 \le M \le 600$. Translated by ChatGPT 5