EduBrick

B. Совершенное паросочетание

2000 мс · 256 МБ · всё или ничего

Дан двудольный граф. Нужно сказать, существует ли паросочетание, покрывающее всю первую долю.

Ответ очевиден из размера: такое паросочетание есть тогда и только тогда, когда максимальное имеет размер nn.

Формат ввода

В первой строке nn и mm (1≤n,m≤20001 \le n, m \le 2000). В следующих nn строках: KiK_i и номера соседей. Сумма KiK_i не превосходит 2⋅1052 \cdot 10^5.

Формат вывода

Выведите YES, если существует паросочетание, покрывающее всю первую долю, и NO иначе.

Примеры

ввод
3 2
2 1 2
1 2
1 2
вывод
NO
ввод
2 2
1 1
1 2
вывод
YES
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.