B. Совершенное паросочетание
2000 мс · 256 МБ · всё или ничего
Дан двудольный граф. Нужно сказать, существует ли паросочетание, покрывающее всю первую долю.
Ответ очевиден из размера: такое паросочетание есть тогда и только тогда, когда максимальное имеет размер .
Формат ввода
В первой строке и (). В следующих строках: и номера соседей. Сумма не превосходит .
Формат вывода
Выведите YES, если существует паросочетание, покрывающее всю первую долю, и NO иначе.
Примеры
ввод
3 2 2 1 2 1 2 1 2
вывод
NO
ввод
2 2 1 1 1 2
вывод
YES
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.