5 ms·

I guess you can just add some edges extra vertices and edges and give all the extra edges probability 1 of being deleted.