Etibarlı şəbəkələr#2622
Kampus binaları arasında şəbəkə dizayn etmək məsuliyyəti sizə həvalə olunub və onun etibarlılığı ilə yanaşı, xərcləri də sizi narahat edir. Bu səbəbdən siz şəbəkəyə bir qədər artıq etibarlılıq əlavə etmək, lakin bunu mümkün qədər ucuz qiymətə saxlamaq qərarına gəlmisiniz. Konkret olaraq, siz elə ən ucuz şəbəkə qurmaq istəyirsiniz ki, istənilən bir xətt sıradan çıksa belə, bütün binalar bir-biri ilə əlaqə saxlaya bilsin. Belə bir şəbəkə minimal etibarlı şəbəkə adlanacaq.
Bir neçə test halı verilir. Hər bir test halı bir sətrdə iki tam ədəd (n \leq 15) və (m \leq 20) — bina sayı (binalar -dən -ə kimi nömrələnib) və binalar arasında mümkün əlaqələrin sayını özündə cəmləşdirir. Sonrakı sətrin hər birində b_1 b_2 (hamısı müsbət tam ədədlər) verilib, burada b_1 və b_2 binalarını birləşdirmək xərc tələb edir. Bütün əlaqələr iki tərəflidir.
Sonuncu test halında n = m = 0 veriləcək və bu hal işləmir.
Hər bir test halı üçün bir sətrdə minimal etibarlı şəbəkənin xərcini verin. Əgər belə bir şəbəkə mövcuddursa, çıxış bu formatda olmalıdır:
The minimal cost for test case is .
burada test halının nömrəsidir (1-dən başlayaraq), isə xərci göstərir. Əgər belə bir etibarlı şəbəkə mövcud deyilsə, aşağıdakı formatda bir sətr çıxış verin:
There is no reliable net possible for test case .
Nümunə 1