Ở một vùng đất nọ, có rất nhiều con người ham học hỏi. Bạn hãy xác định chi phí tối thiểu để cung cấp quyền truy cập thư viện cho tất cả công dân của vùng đất này. Có n thành phố được đánh số từ 1 đến n. Hiện tại không có thư viện và các thành phố không được kết nối với nhau. Đường hai chiều có thể được xây dựng giữa bất kỳ cặp thành phố nào được liệt kê trong mảng cities. Một công dân có quyền truy cập vào thư viện nếu:

• Thành phố của họ có một thư viện
• Họ có thể đi bằng đường bộ từ thành phố của họ đến thành phố có thư viện.

Ví dụ như sau

Hình sau là bản đồ mẫu của Vùng đất nơi các đường chấm biểu thị những con đường có thể có:

Trong đó:

c_road = 2

c_lib = 3

cities = [[1,7], [1, 3], [1,2], [2,3], [5,6], [6,8]]

Chi phí xây dựng bất kỳ con đường nào là c_road = 2 và chi phí để xây dựng một thư viện ở trên thành phố bất kỳ là c_lib = 3. Xây dựng 5 đường xá sẽ tốn 5x2 = 10 chi phí và 2 thư viện sẽ là 3x6 = 6 chi phí. Có q truy vấn, trong đó mỗi truy cấn bao gồm một bản đồ của Vùng dất và giá trị c_lib, c_road. Đối với mỗi truy vấn, bạn hãy tìm chi phí tối thiểu để mọi người dân đề có thể truy cập thư viện.

Input:

int q: số query

int n : số nguyên, số thành phố

int c_lib : integer, chi phí để xây dựng một thư viện

int c_road : integer, chi phí sửa chữa đường

int thành phố [m] [2] : mỗi cities[i] chứa hai số nguyên đại diện cho các thành phố có thể được nối với nhau bằng một con đường mới

Giới hạn

Dòng đầu tiên chứa một số nguyên, biểu thị số lượng truy vấn.

Các dòng tiếp theo mô tả từng truy vấn theo định dạng sau:

• Dòng đầu tiên chứa bốn số nguyên được phân tách bằng dấu cách mô tả các giá trị tương ứng của n, m, c_lib và c_road: số lượng thành phố, số con đường, chi phí của một thư viện và chi phí của một con đường.

• Mỗi cái tiếp theo dòng chứa hai số nguyên được phân tách bằng dấu cách,và, mô tả một con đường hai chiều có thể được xây dựng để kết nối các thành phốvà.

  

  • Mỗi con đường nối hai thành phố riêng biệt.

  

  Giải trình truy vấn 1:

• Có n = 3 thành phố và các thành phố có thể kết nối nhay với m = 3 đường hai chiều. Cái giá của việc xây dựng một thư viện là c_lib = 2 và giá sửa 1 con đường là c_road = 1.

• Cách rẻ nhất để mọi người truy cập thư viện là:
  • Xây dựng 1 thư viện trong thành phố 1 với chi phí x = 2
  • Xây dựng con đường giữa thành phố 1 và 2 với chi phí y = 1
  • Xây dựng con đường giữa thành phố 2 và 3 với chi phí y = 1 => Tổng 2 + 1 + 1 = 4. Lưu ý rằng con đường giữa các thành phố 3 và 1 không cần phải được xây dựng vì mỗi cái được kết nối với thành phố 2.