BANKROB  Bank robbery
The city is plagued with bank robbers, and last year there was a robbery each week in some bank in the city. Police wants to fight this plague, and has to come up with a strategy to solve the problem. One obvious solution would be to place a police patrol at every bank, but this would cost too much money, and because of the crisis it is not possible to choose this solution.
An alternative solution is as follows. Police is alerted about the robbery right after it happened, and can react pretty fast. Robbers use only either motors or cars. Police is able to block any crossroad in the city, and once a crossroad is blocked it is sure that the robbers will be caught if they try to pass the blockage. Moreover, it is possible to forecast some possible destinations of escape from a given bank. Thus the strategy in this case would be to, immediately after a robbery, block some crossroads to make it impossible to reach an escape destination. It would be also great if the number of blockages would be as small as possible, since then the action is cheaper, more effective, and less troublesome for the citizens.
Obviously, if we would compute the smallest number of crossroads that make it impossible to pass from a given bank to given escape points, then this information would be actually useless for the police. Because of the geometry of the city, most likely the smallest set of blockages would consist of couple of crossroads right next to the bank, and by the time police would arrive there, the robbers would be already somewhere else. Thus during the chase, police wants to make realtime decisions that depend on the progress of the situation. To make smart decisions police needs an efficient computer program to compute blockages, and it is your task to write this program. Your program has to read the description of the city map and two locations s and t. It has to compute and return one number, the minimum number of blocked crossroads that will make it impossible to go from location s to location t.
Input
Your program reads from the standard input. In the first line of input you are given two natural numbers n and m (1 < n <= 1000, 1<= m <= 5000), where n is the number of crossroads in the city, and m is the number of streets, where each street connects two crossroads; any two crossroads can be connected by at most one street. Crossroads are numbered from 1 to n. In the line number 2 of the input you are given two numbers s and t, indicating the crossroads that have to be disconnected. In the next m lines of the input you will be given the description of the connections; each such line consists of two numbers c1, c2 and it means that there is a twoway street connecting crossroads c1 and c2.
Output
On the standard output your program has to write one number, the smallest number of crossroads that, when blocked, make it impossible to reach t from s. You may assume that there is no street directly connecting s and t.
Example 1
Input: 10 14
1 10
1 2
1 3
1 4
2 5
3 5
3 6
4 6
5 7
5 8
6 8
6 9
7 10
8 10
9 10 Output: 2
Example 2
Input: 10 14
5 10
1 2
1 3
1 4
2 5
3 5
3 6
4 6
5 7
5 8
6 8
6 9
7 10
8 10
9 10 Output: 3
hide comments
uf0p2rosir:
20190405 21:28:48
Why not just block t and t alone? 

mehmetin:
20131220 10:43:29
first case: 5 6


Kevin Sebastian:
20131220 06:21:50
do we need to use flow algorithms for this one Last edit: 20131226 15:22:19 

mehmetin:
20131216 18:50:42
 Last edit: 20131217 11:54:04 

Kartik Kukreja:
20131215 13:56:42
Please explain the example test cases. In the first test case, how can we make 10 unreachable from 1 by removing any two crossroads? Last edit: 20131215 14:23:20 
Added by:  Marek Adamczyk 
Date:  20131126 
Time limit:  1s50s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 