Yollar və kitabxanalar#11597
Azərbaycan şəhərləri -dən -ə qədər nömrələnmişdir. Hazırda heç bir şəhərdə kitabxana yoxdur və heç bir iki şəhər bir-biri ilə əlaqəli deyil. Giriş məlumatlarında göstərilən şəhər cütləri arasında ikitərəfli yollar tikilə bilər. Şəhərdə kitabxana tikməyin dəyəri -ə bərabərdir. Bir yol tikməyin dəyəri isə -a bərabərdir.
Vətəndaş kitabxanaya çıxış əldə edir, əgər:
Onun şəhərində kitabxana varsa.
O, öz şəhərindən kitabxana olan şəhərə yollarla keçə bilirsə.
Azərbaycanın bütün vətəndaşlarına kitabxanalara çıxışı təmin etməyin minimal dəyərini müəyyən edin.
Birinci sətir testlərin sayı t~(1 \le t \le 10)-u ehtiva edir.
Hər bir testin birinci sətiri dörd tam ədədi ehtiva edir: şəhərlərin sayı n~(1 \le n \le 10^5), yolların sayı m~(1 \le m \le 10^5), kitabxananın dəyəri lib~(1 \le lib \le 10^5) və yolun dəyəri road~(1 \le road \le 10^5). Növbəti sətirdə hər biri iki tam ədəd və olan, və şəhərləri arasında tikilə bilən ikitərəfli yolu təsvir edən cütlər verilmişdir. Hər bir yol iki fərqli şəhəri birləşdirir.
Azərbaycanın bütün vətəndaşlarına kitabxanalara çıxışı təmin etməyin minimal dəyərini çıxarın.
Nümunə 1