For problem F1, I've used Kruskal's algorithm but picking all edges coming out of the maximum degree vertex first and then add other edges which satisfy the spanning tree property.

This resulted in a TLE. Time complexity for the code I have written (in PyPy 3.5) is O(m+n). How can this be improved?