Masala #0147

Baytlandiya davlatida jami N ta shahar bor va ular 1 dan N gacha sonlar bilan tartiblangan, hamda, har bir shaharda bittadan kasalxona mavjud, Baytlandiya davlatida shaharlarni ulab turuvchi jami M ta yo’l mavjud. To’satdan yuzaga kelgan tornado oqibatida Baytlandiya mamlakatidagi barcha kasalxonalar va shaharlarni bog’lab turguvchi yo’llar vayronaga aylandi. Baytlandiya prezidenti barcha shahar fuqarolari uchun zudlik bilan kasalxona muammosini hal qilishi kerak. Uning hisoblashi bo’yicha bitta kasalaxonani qayta qurish uchun A bitosum pul miqdori kerak bo’ladi, bitta yo’lni qayta tiklash uchun esa B bitosum pul miqdori kerak bo’ladi, yangi yo’l qurishning imkoni yo’q. Shahar fuqarosi uchun o’zi yashab turgan shaharda kasalxona mavjud bo’lsa yoki o’zi yashab turgan shahardan kasalxona mavjud bo’lgan qaysidir shaharga borish uchun yo’l mavjud bo’lsa(to’g’ridan to’g’ri bo’lishi shart emas, shaharma-shahar kezib ham borishi mumkin) kasalxonaga borishi mumkin bo’ladi. Mamlakatda iqtisodiy taqchillik bo’lgani bois prezidint bu muammoni imkon qadar kam pul sarflagan holda hal qilishi kerak,  buning uchun unga yordam bering.

INPUT.TXT kirish faylining dastlabki satrida bitta butun son, T(1 ≤ T ≤ 10) testlar soni kiritiladi.

Keyingi qatordan boshlab har bir test uchun quyidagi parametrlar kiritiladi:

Dastlabki satrda to’rtta butun son, N(1 ≤ N ≤ 10⁵), M(0 ≤ M ≤ min(10⁵, )), A, B(1 ≤ A, B ≤ 10⁵).

Keyingi satrdan boshlab M ta satrda u_i va v_i (1 ≤ u_i, v_i ≤ N, u_i ≠ v_i), mos ravishda u_i – shahar va v_i – shaharlar orasida ikki tomonlama yo’l mavjudligini anglatadi.

OUTPUT.TXT chiqish faylida har bir test uchun alohida qatorda bittadan butun son, shaharlar fuqarolari uchun kasalxona muammosini hal qilishga eng kamida necha bitosum miqdorida pul kerakligini chop eting.