There n boys and n girls at a party. Whenever a song starts, they will form exactly n pairs to dance. No boy will dance

[answerhappygod]

There n boys and n girls at a party. Whenever a song starts,they will form exactly n pairs todance. No boy will dance with the same girl twice.Some pairs of boys and girls like each other, and all other pairsof boys and girls dislike each other.Every boy will dance with at most k girls that he dislikes, andeach girl will dance with at most kboys that she dislikes, where k < n.As the DJ, your job is to determine the maximum number of songs youcan play, such that it ispossible for pairs to be formed for all songs according to theabove requirements.
Using maximum flow algorithms, such as Ford-Fulkerson andEdmonds-Karp. Design an algorithm which achieves this and runs intime polynomial in n:
1) For arbitrary k.