Problem Description:
Farmer John owns b bulls and c cows. He also owns b+c fields where each field can hold either one cow or one bull. The fields are located in an area with many hills, so for some pairs of fields the animals in those fields cannot see each other. Unfortunately, his bulls really do not like each other, and neither do his cows. To avoid making any animal angry, John would like to assign the animals to fields such that no two bulls can see each other and no two cows can see each other. Help determine if John can assign his bulls and cows in such a manner.
Input
The first line of input contains n, the number of examples. The first line of each example contains integers b, c, and a where 0 ≤ b, c ≤ 1000 are, respectively, the number of bulls and cows and 0 ≤ a ≤ 20, 000. The next a lines of input each contains two numbers u and v which indicates that animals placed in fields u and v can see each other. Fields are numbered from 1 to b + c.
I think that it is a bicoloring problem . If bicoloring fail ans must be no ,otherwise yes. But it give Wrong Answer.I got some tag for this problem DP+Knapsack .But I can not understood why need dp and knapsack .
I didn't solve this yet (I'll do it tomorrow since it's 2AM here), but you have to think on these problems:
If you have a bipartite graph doesn't mean you can solve the problem since you can have 2 sets of vertices, each one having a different color, that have sizes different than b and c.
So you have to get all different bipartite sets and do a knapsack to see if you can get exactly the sizes you want (b and c).
That's why it's on DP + Knapsack section.