Description

The experimental center can be regarded as an undirected connected graph with $n$ vertices and $m$ edges.
Every second, each experimenter can move to an adjacent laboratory and collect the data there, while the toxic gas spreads every second to all adjacent laboratories.
When an experimenter returns to the hall $s$, we say that they have rescued the data.
Experimenters cannot enter laboratories filled with toxic gas (and it is also not allowed if they and the gas enter the same laboratory in the same second).
There are strict protection measures around the hall, so it will not be reached by the toxic gas. (See Sample 2 for details.)
Now all experimenters are in the hall $s$, and the laboratory where the gas leaks is vertex $t$. Assuming there are enough experimenters to depart at the same time, what is the maximum number of laboratories’ data that can be rescued?

Input Format

The first line contains two positive integers $n, m$, indicating the number of vertices and edges in the experimental center.
Lines $2$ to $m + 1$ each contain two positive integers $u, v$, indicating that there is an edge between laboratories $u$ and $v$.
Line $m + 2$ contains two positive integers $s, t$, indicating the hall and the gas leak vertex.

Output Format

Output one integer in a single line, indicating the maximum number of laboratories whose data can be rescued.

4 3
1 2
2 3
3 4
1 4

1

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

2

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

6

Hint

Please pay attention to the impact of constant factors on runtime efficiency.

[Sample Explanation 1]
Only Laboratory $2$ can be reached and then returned from.

[Sample Explanation 2]
Because the hall is indestructible, Laboratories $5$ and $6$ will be reached by the gas, while Laboratories $2$ and $3$ will never be reached by the gas.

[Sample Explanation 3]
The vertices that can be rescued are: $2, 3, 4, 5, 11, 12$.

[Constraints]
This problem uses bundled testdata.
For $10\%$ of the testdata, $2 \leq n, m \leq 20$;
For $30\%$ of the testdata, $2 \leq n \leq 2000, 1 \leq m \leq 10000$;
For $70\%$ of the testdata, $2 \leq n \leq 2 \times 10^5$;
For $100\%$ of the testdata, $2 \leq n, m \leq 5 \times 10^6$.

Since the input size is very large, here is the fast input template used in the std (you need to choose C++11 or above when submitting).

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. It can read any number of values, but it cannot be used together with std::cin or std::scanf. After finishing input, press Ctrl+Z on Windows, or Ctrl+D on Linux to end.

Translated by ChatGPT 5