Олимпиадный тренинг

Задача . Decorating the Pastures


Задача

Темы: графы Поиск компонент связности поиск в глубину и подобное

У Фермера Джона имеется N (1 <= N <= 50,000) пастбищ, последовательно пронумерованных от 1 до N, соединённых M (1 <= M <= 100,000) двунаправленными дорогами. Дорога I соединяет пастбища Ai (1 <= Ai <= N) и Bi (1 <= Bi <= N), Ai != Bi. Возможны две дороги соединяющие одну и ту же пару пастбищ.
Беси хочет украсить пастбища к дню рождения ФД. Она хочет разместить на каждом пастбище огромный знак содержащий либо букву ‘F’ либо букву ‘J’, но чтобы не огорчать ФД, должно быть выполнено правило, Пастбища декорируются разными знаками, если они соединены дорогой.
Компания, изготавливающая знаки, требует больше денег за знак ‘F’ и меньше денег за знак ‘J’, поэтому Беси хочет максимизировать количество знаков ‘J’, которые она использует. Пожалуйста, определите это число или выведите -1, если невозможно расставить знаки по описанным правилам.
uses. Please determine this number, or output -1 if there is no valid way to arrange the signs.
PROBLEM NAME: decorate
Формат ввода:
* Строка 1: Два целых числа N и M.
* Строки 2..M+1: Два целых числа, Ai и Bi указывающих наличие двунаправленной дороги между пастбищами Ai и Bi.
Примечание
Пастбища и дороги представляют собой вершины и стороны квадрата.
Формат вывода:
* Строка 1: Одно целое число, указывающее максимальное количество знаков ‘J’ которые сможет использовать Беси. Если нет решения, то выводить -1.
Примечание
Беси может пометить пастбища 1 и 3 знаком ‘J’ (или альтернативно - пастбища 2 и 4).
Примеры
№Входные данныеВыходные данные
1 
4 4
1 2
2 3
3 4
4 1
 
2
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет