Tom and Jerry - MarisaOJ: Marisa Online Judge

Tom and Jerry

Time limit: 1000 ms
Memory limit: 256 MB
Jerry is being chased by Tom on a connected graph of $n$ vertices and $m$ edges. Jerry is currently at vertex $a$, and Tom is currently at vertex $b$. They both need $1$ unit of time to run from a vertex to another. You can choose to stand at a vertex. If Jerry can arrive at your vertex no later than Tom, you can save Jerry. In how many vertices can you stand in order to save Jerry? ### Input - The first line contains 2 integers $n, m$. - The second line contains 2 integers $a, b$. - The next $m$ lines, each line contains 2 integers $u, v$, there is an edge between $u$ and $v$. ### Output - Print the number of vertices you can choose to stand at to save Jerry. ### Constraints - $1 \le n, m \le 10^5$. - $1 \le u, v,a, b \le n$. ### Example Input: ``` 6 6 3 5 1 2 1 5 2 3 2 4 4 5 4 6 ``` Output: ``` 2 ``` #### **Note**: You can choose to stand at either $2$ or $3$.