Ở Nhật Bản, các thành phố được kết nối bằng mạng lưới các con đường cao tốc. Mạng lưới này gồm \(N\) thành phố và \(M\) con đường cao tốc. Mỗi con đường cao tốc nối một cặp hai thành phố khác nhau. Không có hai con đường cao tốc nối cùng một cặp hai thành phố. Các thành phố được đánh số từ \(0\) đến \(N-1\), và các con đường cao tốc được đánh số từ \(0\) đến \(M-1\). Bạn có thể lái xe trên mỗi con đường cao tốc theo cả hai chiều. Bạn có thể đi từ một thành phố bất kỳ sang một thành phố bất kỳ khác qua những con đường cao tốc.

Phải mua vé khi lái xe trên mỗi con đường cao tốc. Giá vé cho mỗi con đường cao tốc phụ thuộc vào độ tắc nghẽn của con đường. Độ tắc nghẽn có thể là thưa hoặc dày. Khi độ tắc nghẽn là thưa, giá vé là \(A\) yen (đơn vị tiền tệ Nhật Bản). Khi độ tắc nghẽn là dày, giá vé là \(B\) yen. Đảm bảo rằng \(A<B\). Chú ý là bạn biết giá trị của \(A\) và \(B\).

Bạn có một cỗ máy, khi được cho độ tắc nghẽn của tất cả các con đường cao tốc, nó tính ra tổng giá vé nhỏ nhất phải trả khi di chuyển giữa cặp hai thành phố \(S\) và \(T\) (\(S \ne T\)), trong trạng thái giao thông đó.

Tuy nhiên, cỗ máy này mới chỉ ở dạng thử nghiệm. Giá trị \(S\) và \(T\) cố định (tức là được cài đặt cố định vào cỗ máy) và bạn không biết các giá trị này. Bạn phải xác định giá trị của \(S\) và \(T\). Để thực hiện điều này, bạn lên kế hoạch nhập vào cỗ máy một số bộ giá trị độ tắc nghẽn, và sử dụng tổng giá vé mà cỗ máy tính ra để xác định \(S\) và \(T\). Vì việc nhập vào các độ tắc nghẽn là tốn kém, bạn không muốn sử dụng cỗ máy nhiều lần.

Chi tiết cài đặt

Bạn phải cài đặt thủ tục sau, với chữ ký C++ trong tệp highway.h của gói đính kèm:

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B);

• N: số lượng các thành phố.
• U và V: các mảng độ dài \(M\), với \(M\) là số lượng các con đường cao tốc nối giữa các thành phố. Với mỗi \(i\) (\(0 \le i \le M-1\)), con đường cao tốc thứ \(i\) nối hai thành phố U[i] và V[i].
• A: giá vé trên con đường cao tốc với độ tắc nghẽn là thưa.
• B: giá vé trên con đường cao tốc với độ tắc nghẽn là dày.
• Thủ tục này được gọi đúng một lần cho mỗi bộ dữ liệu.
• Chú ý rằng \(M\) là độ dài của các mảng; cách lấy độ dài mảng được mô tả trong Lưu ý cài đặt.

Thủ tục find_pair có thể gọi hàm sau:

long long ask(const std::vector<int> &w);

• Độ dài của w phải đúng bằng \(M\). Mảng w mô tả độ tắc nghẽn.
• Với mỗi \(i\) (\(0 \le i \le M-1\)), w[i] mô tả độ tắc nghẽn trên con đường cao tốc thứ \(i\). Giá trị của w[i] phải là \(0\) hoặc \(1\): w[i] = 0 nghĩa là độ tắc nghẽn trên con đường đó là thưa; w[i] = 1 nghĩa là độ tắc nghẽn trên con đường đó là dày.
• Hàm này trả lại tổng giá vé nhỏ nhất khi di chuyển giữa hai thành phố \(S\) và \(T\), với trạng thái giao thông được xác định bởi w. Giá trị trả về là số nguyên \(64\) bit.
• Hàm này được gọi tối đa \(100\) lần cho mỗi bộ dữ liệu.

find_pair phải gọi thủ tục sau để báo cáo kết quả:

void answer(int s, int t);

• s và t phải là cặp \(S\) và \(T\) (thứ tự không quan trọng).
• Thủ tục này phải được gọi đúng một lần.

Nếu một trong những điều kiện trên không thỏa mãn, chương trình của bạn được chấm là Wrong Answer. Ngược lại, chương trình được chấm là Accepted và điểm số của bạn được tính dựa trên số lần gọi ask (xem phần Subtasks).

Ví dụ

Giả sử \(N=4\), \(M=4\), \(U=[0,0,0,1]\), \(V=[1,2,3,2]\), \(A=1\), \(B=3\), \(S=1\) và \(T=3\).

Trình chấm gọi find_pair(4, [0, 0, 0, 1], [1, 2, 3, 2], 1, 3).

Trong hình trên, cạnh có số thứ tự \(i\) tương ứng với con đường cao tốc thứ \(i\). Một số lời gọi ask có thể và giá trị trả về tương ứng được liệt kê dưới đây:

Với lời gọi ask([0, 0, 0, 0]), độ tắc nghẽn của tất cả các con đường cao tốc là thưa và giá vé cho mỗi con đường là \(1\). Tuyến đường có chi phí thấp nhất từ \(S=1\) tới \(T=3\) là \(1 \to 0 \to 3\). Tổng giá vé trên tuyến đường này là \(2\). Do đó, hàm này trả về giá trị \(2\).

Để đưa ra câu trả lời đúng, thủ tục find_pair phải gọi answer(1, 3) hoặc answer(3, 1).

Tệp sample-01-in.txt trong gói nén zip đính kèm tương ứng với ví dụ này. Gói đính kèm cũng chứa dữ liệu đầu vào của các ví dụ khác.

Hạn chế

• \(2 \le N \le 90\,000\).
• \(1 \le M \le 130\,000\).
• \(1 \le A < B \le 1\,000\,000\,000\).
• Với mỗi \(i\) (\(0 \le i \le M-1\)): \(0 \le U[i] \le N-1\), \(0 \le V[i] \le N-1\) và \(U[i] \ne V[i]\).
• \((U[i],V[i]) \ne (U[j],V[j])\) và \((U[i],V[i]) \ne (V[j],U[j])\) (\(0 \le i < j \le M-1\)).
• Bạn có thể đi từ một thành phố bất kỳ đến bất kỳ thành phố nào còn lại bằng các con đường cao tốc.
• \(0 \le S \le N-1\).
• \(0 \le T \le N-1\).
• \(S \ne T\).

Trong bài này, trình chấm không có tính thích nghi. Điều này có nghĩa là \(S\) và \(T\) được cố định ngay từ đầu khi trình chấm chạy và không phụ thuộc vào các truy vấn do chương trình của bạn đưa ra.

Phân nhóm

Giả sử chương trình của bạn được chấm là Accepted và gọi ask \(X\) lần. Tùy theo subtask, điểm số \(P\) của bạn cho bộ dữ liệu được tính như sau:

Điểm của bạn cho mỗi subtask là điểm nhỏ nhất của các bộ dữ liệu trong subtask đó.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu đầu vào theo khuôn dạng sau:

• Dòng \(1\): \(N\ M\ A\ B\ S\ T\).
• Dòng \(2+i\) (\(0 \le i \le M-1\)): \(U[i]\ V[i]\).

Nếu chương trình của bạn được chấm là Accepted, trình chấm mẫu in Accepted: q, với q là số lần gọi ask.

Nếu chương trình của bạn được chấm là Wrong Answer, trình chấm mẫu in Wrong Answer: MSG, trong đó MSG có thể là:

Dữ liệu vào của ví dụ trên:

4 4 1 3 1 3
0 1
0 2
0 3
1 2

Nếu chương trình thực hiện đúng bốn lời gọi ask trong bảng rồi gọi answer(1, 3), trình chấm mẫu in:

Accepted: 4