The time-limit for this problem is a bit tight. Similar problems p1489_Find_Critical_and_Pseudo-Critical_Edges_in_Minimum_Spanning_Tree p1568_Minimum_Number_of_Days_to_Disconnect_Island