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≤n,m≤105.
- 1≤u,v,a,b≤n.
### Example
Input:
6635121523244546
Output:
2
#### **Note**: You can choose to stand at either 2 or 3.
