The publicity team for Technozion is in full swing. Like every year, this time too, the team is planning to visit N different colleges in India. This publicity campaign shall involve the members of the team giving presentations about Technozion.
For the publicity trip, the team has decided to come up with two different types of presentations(Presentation A and Presentation B) to be delivered at the colleges they visit.
Your job is to help them carry on this task in a more organized manner.
You shall be given with the total number of students (population) studying in each college, as well as the highways between the colleges. You need to help the team plan a trip such that no two colleges which are connected directly by a highway are given the same presentation and such that the difference between the number of students who attend the Presentation A and those who attend the Presentation B is minimal .
Your final task is to help out our team by providing them with the absolute minimal difference between the number of students who will attend Presentation A and who will attend Presentation B ,so that all the conditions above are satisfied.
Input Format :
First line of the input contains a single integer M, the number of bi-directional Highways.
Then M lines describing bi-directional Highways follow, each of them contains two integers (u, v) representing a
Highway connecting college u and college v.
After this Follow a single line containg an Integer N (Numbered 0 to N-1) indicating the total Number of colleges.
Then Follows N Lines ,each containing a single integer indicating the total number of student in ith college.
Output Format:
For each test case, output a single integer - the absolute minimal difference between the number of students who will attend
Presentation A and who will attend Presentation B,as described above.
Please give me hint in this question how to proceed. :)