Problem Background

A laboratory in a large experimental center has experienced a toxic gas leak. Now, the lab technicians want to salvage the experimental data.

Problem Description

The experimental center can be viewed as an undirected connected graph with $n$ vertices and $m$ edges.
All lab technicians can move to an adjacent laboratory each second and collect the data therein. The toxic gas spreads to all adjacent laboratories each second.
When a lab technician returns to the lobby $s$, we say they have salvaged the data.
Lab technicians cannot enter laboratories that have been contaminated by the gas (even if they enter the laboratory at the same second as the gas).
The lobby is surrounded by strict protective measures and will not be affected by the gas spread. (Refer to Sample 2 for details)
Now, all lab technicians are in the lobby $s$, and the laboratory where the gas leaked is at vertex $t$. Assuming there are enough technicians starting simultaneously, what is the maximum number of laboratories from which data can be salvaged?

Input Format

The first line contains two positive integers $n, m$, representing the number of vertices and edges in the experimental center.
From the second to the $(m+1)$-th line, each line contains two positive integers $u, v$, indicating an edge between laboratories $u$ and $v$.
The $(m+2)$-th line contains two positive integers $s, t$, representing the lobby and the point of gas leakage.

Output Format

A single integer on one line, indicating the maximum number of laboratories from which data can be salvaged.

Sample Input and Output

Sample Input 1

4 3
1 2
2 3
3 4
1 4

Sample Output 1

1

Sample Input 2

6 7
1 2
2 3
3 1
4 5
5 6
6 4
1 4
1 4

Sample Output 2

2

Sample Input 3

15 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
3 11
11 12
12 13
13 14
14 15
1 10

Sample Output 3

6

Notes

Please be aware of the impact of constant factors on program efficiency.

Sample Explanation 1
Only laboratory 2 can be reached and returned from.

Sample Explanation 2
Since the lobby is indestructible, laboratories 5 and 6 will be affected by the gas, while laboratories 2 and 3 will never be affected.

Sample Explanation 3
The laboratories that can be salvaged are: 2, 3, 4, 5, 11, 12.

Data Range
This problem uses bundled testing.
For $10\%$ of the data, $2 \leq n, m \leq 20$;
For $30\%$ of the data, $2 \leq n \leq 2000, 1 \leq m \leq 10000$;
For $70\%$ of the data, $2 \leq n \leq 2 \times 10^5$;
For $100\%$ of the data, $2 \leq n, m \leq 5 \times 10^6$.

Due to the large amount of input, a fast reading template used by the standard solution is provided here (submission requires C++11 or above):

char gc() {
  static char now[1 << 20], *S, *T;
  if (T == S) {
    T = (S = now) + std::fread(now, 1, 1 << 20, stdin);
    if (T == S) return EOF;
  }
  return *S++;
}
template <typename T>
void Read(T &x) {
  x = 0;
  char c = gc();
  while (c < '0' || c > '9') c = gc();
  x = c - '0';
  while ((c = gc()) >= '0' && c <= '9') x = x * 10 + c - '0';
}
template <typename T, typename... Args>
void Read(T &x, Args &... args) {
  Read(x);
  Read(args...);
}

Usage: Read(n, m) or Read(x, y, z), etc., can read any number of inputs but should not be used together with std::cin and std::scanf. After input, press Ctrl+Z on Windows or Ctrl+D on Linux to end the input.

见题面 Input 部分

见题面 Output 部分