Một loài sinh vật độc đáo và bí ẩn tên là Nuko sinh sống trên một quần đảo xa xôi. Quần đảo được mô hình hóa bởi \(N\) hòn đảo, đánh số từ \(0\) đến \(N-1\), và \(M\) cây cầu. Cầu thứ \(i\) nối hai đảo phân biệt \(U[i]\), \(V[i]\) theo cả hai chiều. Không có hai cầu nào nối cùng một cặp đảo, và có thể đi giữa mọi cặp đảo.

Thời xa xưa, Nuko chỉ sống trên đảo \(0\). Sau một thời gian dài, chúng đã lan ra mọi hòn đảo. Mỗi khi một nhóm Nuko đi qua một cây cầu đến đảo mới, chúng tiến hóa thành một phân loài khác với phân loài ở đảo trước đó.

Cụ thể, Nuko trên đảo \(j\) thuộc phân loài \(s_j\), trong đó \(s_j\) là số cầu ít nhất phải đi qua để đến đảo \(j\) từ đảo \(0\). Chẳng hạn, Nuko trên đảo \(0\) thuộc phân loài \(0\).

Bạn muốn đi từ đảo \(A\) đến đảo \(B\) bằng các cây cầu; luôn có \(A\ne B\). Khi đặt chân lên một hòn đảo, bạn chắc chắn gặp phân loài Nuko sống ở đó. Vì mỗi phân loài có tập tục riêng và việc thích nghi với nhiều tập tục rất phiền phức, bạn muốn chọn một đường đi sao cho số phân loài Nuko phân biệt gặp phải là nhỏ nhất.

Hãy tìm số phân loài phân biệt ít nhất phải gặp trên hành trình từ \(A\) đến \(B\).

Yêu cầu cài đặt

Bạn cần cài đặt hàm sau:

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

• \(N\) là số đảo và \(M\) là số cầu.
• \(A,B\) lần lượt là đảo bắt đầu và đảo kết thúc.
• \(U,V\) là hai mảng độ dài \(M\) mô tả các cây cầu.
• Hàm phải trả về số phân loài Nuko phân biệt ít nhất phải gặp.

Bài nộp không được cài đặt hàm main và phải khai báo #include "trip.h".

Giới hạn

• \(2\le N\le 5\,000\,000\).
• \(1\le M\le 5\,000\,000\).
• \(0\le A,B<N\) và \(A\ne B\).
• \(0\le U[i],V[i]<N\) và \(U[i]\ne V[i]\) với mọi \(0\le i<M\).
• Với mọi \(i\ne j\), hai cặp \((U[i],V[i])\) và \((U[j],V[j])\) không biểu diễn cùng một cạnh theo bất kỳ thứ tự nào.
• Đồ thị liên thông.

Chấm điểm

Trong phần 9, riêng trình chấm được đảm bảo sử dụng \(1500\) ms trong giới hạn thời gian \(4500\) ms.

Ví dụ

Ví dụ 1

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

Đường đi tối ưu là \(2-3-4\). Các phân loài gặp phải là \(1\) và \(2\), nên hàm trả về 2.

Ví dụ 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])

Đường đi tối ưu là \(4-1-5-2-6-3-7\). Các phân loài gặp phải là \(1\) và \(2\), nên hàm trả về 2.

Ví dụ 3

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])

Số phân loài phân biệt ít nhất phải gặp khi đi từ đảo \(3\) đến đảo \(7\) là \(3\), nên hàm trả về 3.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng:

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

và in một số nguyên là giá trị do min_distinct trả về.

Nguồn: Southeast Asia Team Selection Test 2026, Ngày 2, bài Troublesome Trip.