Снова танцы. На вечеринку приглашены n мальчиков и n девочек. Они хотят станцевать несколько раундов.

[email protected] в категроии Разное, вопрос открыт 09.04.2018 в 10:54

В каждом раунде гости делятся на n танцующих пар. Каждый гость должен быть в некоторой паре, каждая пара должна состоять из одного мальчика и одной девочки. В каждом раунде каждый мальчик должен танцевать с другой девочкой. Некоторые мальчики и девочки не нравятся друг другу. Каждый мальчик может танцевать не более чем с k девочками, которые ему не нравятся. Аналогично каждая девочка может танцевать не более чем с k мальчиками, которые ей не нравятся. Имеется информация о том, нравятся ли друг другу i-ый мальчик и j-ая девочка (1 ≤ i, j ≤ n). Найти наибольшее количество раундов, которое можно станцевать на вечеринке.