### PROBLEM LINK:

**Author:** Vinod

**Tester:** Vinod

**Editorialist:** Manjunath

### DIFFICULTY:

MEDIUM

### PREREQUISITES:

Binary Search, DFS of graph

### PROBLEM:

Graph edges are being deleted one per day.We have to find sum of cost of days when graph can be colored using 2 colors such that no two vertices adjacent to each other colored with same color.Cost of day is considered as edges removed till that day.

### QUICK EXPLANATION:

once the graph can be colored with 2 colors,after removing some more edges

also,it can be colored with 2 colors.So,we need to find first day when it can be colored using two vertices.then all days after that can also be colored with 2 colors till last day.we can easily find sum of those costs.

### EXPLANATION:

once the graph can be colored with 2 colors,after removing some more edges

also,it can be colored with 2 colors.So,we need to find first day when it can be colored using two vertices.then all days after that can also be colored with 2 colors till last day.we can easily find sum of those costs.

we can binary search for the first day.

int cnt=count of edges; int lo=0,hi=cnt,ans=-1; while(lo<=hi){ int mid=(lo+hi)/2; if(can_be_colored(mid)){ // remove edges upto mid [0..mid) days not considering mid ans=mid; hi=mid-1; } else lo=mid+1; } //by removing at least ans edges ,graph can be colored with 2 colors. final_answer=((cnt)* (cnt+1) )/2 - (ans * (ans+1))/2;

### AUTHOR’S AND TESTER’S SOLUTIONS:

Tester’s solution can be found here.