Səsvermə#5489
Baytlandiyada səsvermə keçirmək qərara alınıb. Səs vermək üçün hər bir şəxs ən yaxın səsvermə məntəqəsinə getməlidir. Baytlandiya sakinləri tənbəl olduğundan, əgər onların yaşadığı yerdən səsvermə məntəqəsinə səyahət bir gündən çox çəkərsə, səsverməyə getməyəcəklər. Baytlandiya istiqamətsiz qraf şəklindədir və hər bir yol üzrə səyahət vaxtı tam olaraq bir gündür. Ölkənin hər bir yolu boyunca insanlar yaşayır (yol boyunca bərabər şəkildə və çox sıx). Səsvermə məntəqələri yalnız zirvələrdə tikilə bilər. Buna görə də, hər kəsin səs verməsi üçün (yəni səsverməyə getməsi üçün) hər bir kənarın iki ucundan birində səsvermə məntəqəsi olmalıdır.
Ölkənin hökmdarına pul qənaət etməkdə və səsvermə məntəqələrinin tikilməsi lazım olan minimum ölçülü zirvələr dəstini seçməkdə kömək etmək lazımdır.
Birinci sətirdə qrafın zirvələrinin və kənarlarının sayı olan N və M ədədləri (1 ≤ N ≤ 50000, 1 ≤ M ≤ 100000) verilir. Növbəti M sətir hər biri 2 ədəd - a və b (1 ≤ a, b, ≤ N, a ≠ b) ehtiva edir ki, bu da a və b şəhərləri arasında yol olduğunu göstərir.
Çıxış faylı iki sətirdən ibarət olmalıdır - birinci sətirdə zirvələrin sayı k və ikinci sətirdə 1 ilə n arasında k ədəd.
Qeyd
Real müsabiqədə qiymətləndirmə belə aparılırdı:
Siz giriş testlərini yükləyə bilərdiniz.
Çıxış testləri, proqram deyil, qiymətləndirilirdi.
Əgər sizin k zirvələriniz bütün m kənarları əhatə etmirsə, test üçün 0 bal alacaqsınız. Əgər cavab düzgün olarsa, seçdiyiniz dəstin ölçüsündən asılı olaraq bal verilir. Tutaq ki, sizin cavabınız = y, optimal = b. Onda siz 10·((8b-7y)/b)^2 bal qazanacaqsınız (ən yaxın tam ədədə yuvarlaqlaşdırılmış).
Biz riskə gedərək eksperiment etməyə və məhz sizin proqramınızı qiymətləndirməyə cəsarət etdik.
Nümunə 1