*Please provide solution in Python or C++*

*Must be able to pass test cases up so sizes according to the constraints*

*It is essentially a Min Vector Cover Problem but not an approximation, it uses Branch-and-Bound*

Example Input (first line indicates 5 villages (numbered 0 through 4) and 6 roads (each following line))

5 6

0 1

0 2

0 4

1 4

2 3

2 4

Example Output

3

I am taking over villages that will allow me to gain control of my region. I must determine the smallest number of villages that I can control to make sure that I have a presence on at least one side of every single village. Hint: A branch-and-bound approach is needed to come up with a solution to this problem. Input Format The first line contains two values, the number of villages (N) and the number of roads linking villages (M) The next M lines each describe a road, indicating the village ID on either side. Constraints 1 s N s 200 1 s M s 10,000 0 s Village IDsN Output Format A single number indicating the minimum number of villages that can possibly be controlled to make sure that one is controlled on at least one side of every road