Một loài sinh vật độc đáo và bí ẩn được gọi là Nuko sinh sống trên một quần đảo ở một vùng xa xôi của thế giới. Quần đảo này có thể được mô hình hóa với $N$ hòn đảo, được đánh số từ $0$ đến $N - 1$, kết nối với nhau bởi $M$ cây cầu. Mỗi cây cầu $i$ nối hai hòn đảo $U[i]$ và $V[i]$, với mọi $0 \leq i \leq M - 1$, theo cả hai hướng. Có thể đi đến bất kỳ hòn đảo nào từ bất kỳ hòn đảo nào khác. Mỗi cây cầu nối hai hòn đảo phân biệt và không có hai cây cầu nào nối cùng một cặp hòn đảo.

Thời xa xưa, Nuko chỉ sinh sống trên đảo $0$. Tuy nhiên, sau một thời gian dài, Nuko đã lan rộng ra tất cả các hòn đảo. Mỗi khi một nhóm Nuko băng qua một cây cầu để đến một hòn đảo mới, chúng sẽ tiến hóa, dẫn đến một phân loài khác so với những cá thể ở hòn đảo trước đó. Cụ thể, đối với đảo $j$, với mọi $0 \leq j \leq N - 1$, các Nuko thuộc phân loài $s_j$, bằng với số lượng cây cầu ít nhất cần phải băng qua để đi từ đảo $0$ đến đảo $j$. Ví dụ, Nuko trên đảo $0$ thuộc phân loài $0$.

Bạn là một du khách đang muốn thực hiện hành trình từ đảo $A$ đến đảo $B$ bằng cách sử dụng các cây cầu. Đảm bảo rằng $A \neq B$. Khi bạn ở trên một hòn đảo nào đó, bạn chắc chắn sẽ gặp phân loài Nuko sống ở đó. Vì mỗi phân loài có phong tục riêng và việc thích nghi với các phong tục khác nhau có thể gây rắc rối, mục tiêu của bạn là chọn một lộ trình giúp giảm thiểu số lượng phân loài Nuko khác nhau mà bạn gặp phải.

Bạn có thể xác định số lượng phân loài Nuko khác nhau tối thiểu mà bạn phải gặp khi đi từ đảo $A$ đến đảo $B$ không?

Chi tiết cài đặt

Bạn cần cài đặt thủ tục sau:

int min_distinct(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V)

• $N$: số lượng hòn đảo.
• $M$: số lượng cây cầu.
• $A$: điểm bắt đầu hành trình của bạn.
• $B$: điểm kết thúc hành trình của bạn.
• $U$, $V$: các mảng có độ dài $M$ mô tả các cây cầu.
• Thủ tục này cần trả về số lượng phân loài Nuko khác nhau tối thiểu mà bạn phải gặp.

Giới hạn

• $2 \le N \le 5\,000\,000$.
• $1 \le M \le 5\,000\,000$.
• $0 \le A, B \le N - 1$.
• $A \neq B$.
• $0 \le U[i], V[i] \le N - 1$, với mọi $0 \leq i \leq M - 1$.
• $U[i] \neq V[i]$, với mọi $0 \leq i \leq M - 1$.
• $(U[i], V[i]) \neq (U[j], V[j])$ và $(U[i], V[i]) \neq (V[j], U[j])$, với mọi $0 \leq i, j \leq M-1$ và $i \neq j$.
• Đảm bảo rằng có thể đi đến bất kỳ hòn đảo nào từ bất kỳ hòn đảo nào khác.

Nhiệm vụ con

1. (4 điểm) $A = 0$, $N \le 100\,000$, $M \le 100\,000$.
2. (4 điểm) $M = N - 1$, $N \le 100\,000$, $M \le 100\,000$.
3. (6 điểm) $N \le 300$, $M \le 300$.
4. (8 điểm) $N \le 4\,000$, $M \le 4\,000$.
5. (22 điểm) $N \le 4\,000$, $M \le 1\,000\,000$.
6. (14 điểm) $N \le 100\,000$, $M \le 100\,000$.
7. (5 điểm) $N \le 300\,000$, $M \le 300\,000$.
8. (5 điểm) $N \le 500\,000$, $M \le 500\,000$.
9. (32 điểm) Không có giới hạn bổ sung.

Ghi chú: Đối với nhiệm vụ con 9, riêng trình chấm đã được đảm bảo tiêu tốn 1500ms trong giới hạn thời gian 4500ms.

Ví dụ

Xem xét các lời gọi sau.

min_distinct(5, 5, 2, 4, [0, 1, 2, 3, 4], [1, 2, 3, 4, 0])

Các hòn đảo có thể được minh họa như dưới đây, với các sắc thái khác nhau đại diện cho các phân loài Nuko khác nhau.

Đối với ví dụ 1, lộ trình tối ưu là $2-3-4$. Các phân loài Nuko gặp phải là $1$ và $2$. Do đó, lời gọi này sẽ trả về $2$.

min_distinct(8, 9, 4, 7, [0, 0, 0, 1, 1, 2, 2, 6, 7], [1, 2, 3, 4, 5, 5, 6, 3, 3])

Các hòn đảo có thể được minh họa như dưới đây, với các sắc thái khác nhau đại diện cho các phân loài Nuko khác nhau.

Đối với ví dụ 2, lộ trình tối ưu là $4-1-5-2-6-3-7$. Các phân loài Nuko gặp phải là $1$ và $2$. Do đó, lời gọi này sẽ trả về $2$.

min_distinct(15, 17, 3, 7,
              [0, 1, 2, 3, 4, 13, 12, 12, 11, 10, 10, 9, 8, 7, 6, 8, 0],
              [1, 2, 3, 4, 13, 12, 1, 11, 10, 9, 5, 8, 7, 6, 5, 14, 14])

Đối với ví dụ 3, số lượng phân loài Nuko khác nhau tối thiểu mà bạn phải gặp khi đi từ đảo $3$ đến đảo $7$ là $3$. Do đó, lời gọi này sẽ trả về $3$.

Trình chấm mẫu

Dữ liệu vào:

N M A B
U[0] V[0]
U[1] V[1]
...
U[M - 1] V[M - 1]

Dữ liệu ra:

Một số nguyên đại diện cho giá trị trả về của min_distinct.