Голосування#5489
У Байтляндії було вирішено провести голосування. Щоб проголосувати, людині потрібно під'їхати до найближчого пункту голосування. Жителі Байтляндії ліниві. Якщо подорож від місця, де вони живуть, до пункту голосування триває більше одного дня, вони на голосування не підуть. Байтляндія має вигляд неорієнтованого графа. Час подорожі кожною з доріг — рівно один день. Вздовж кожної дороги країни живуть люди (рівномірно по дорозі й дуже густо). Пункти голосування можна будувати лише у вершинах. Відповідно, щоб усі проголосували (тобто пішли на голосування), потрібно, щоб у кожного ребра в одному з двох кінців був пункт голосування.
Необхідно допомогти правителю країни зекономити гроші і вибрати мінімальну за розміром множину вершин, у яких потрібно спорудити пункти голосування.
У першому рядку числа та — кількість вершин та ребер графа відповідно (1 \leq N \leq 50000, 1 \leq M \leq 100000). Наступні рядків містять по числа — та (1 \leq a, b \leq N, a \neq b), що означає, що між містами та є дорога.
Вихідний файл повинен складатися з двох рядків — число вершин у першому рядку та чисел від до у другому.
Приклад 1
На реальному контесті оцінювання відбувалося так:
Ви могли скачати вхідні тести.
Оцінювалися вихідні тести, а не програма.
Якщо ваші вершин не покривають усі ребер, ви отримаєте 0 балів за тест. Якщо ж відповідь коректна, число балів залежить від розміру вибраної вами множини. Нехай ваша відповідь — , а оптимальна — . Тоді ви заробите 10 \cdot ((8b-7y)/b)^2 балів (округлені до найближчого цілого).
Ми ризикнули піти на експеримент і на свій страх та ризик оцінити саме вашу програму.
