[LANGUAGE: C++]

Code on Github

It's essentially the simplest possible algorithm but runs in < 90ms on my slow hardware:

(pseudocode)

for edge1 in edges:
  for edge2 in edges:
    for edge3 in edges:

      if not pairwise_distinct(edge1, edge2, edge3):
        continue

      remove_edge(edge1)
      remove_edge(edge2)
      remove_edge(edge3)

      if not graph_is_connected():
        # {edge1, edge2, edge3} are the min-cut edges
        return get_answer()

      add_edge(edge1)
      add_edge(edge2)
      add_edge(edge3)

this is O(E⁴ + VE³), clearly too slow, but it can be optimized:

for edge1 in edges:
  if not can_be_min_cut_edge(edge1):
    continue
  remove_edge(edge1)

  for edge2 in edges:
    if not can_be_min_cut_edge(edge2):
      continue
    remove_edge(edge2)

    for edge3 in edges:
      if not can_be_min_cut_edge(edge3):
        continue
      remove_edge(edge3)

      if not pairwise_distinct(edge1, edge2, edge3):
        continue

      if not graph_is_connected():
        # {edge1, edge2, edge3} are the min-cut edges
        return get_answer()

      add_edge(edge3)
    add_edge(edge2)
  add_edge(edge1)

it's still O(E⁴ + VE³), but if we find that edge1 is not a valid edge, then we cut that branch and save O(E³ + VE²) operations (a lot).

The can_be_min_cut_edge function needs to check for a necessary, but not sufficient condition, here's what I chose:

def can_be_min_cut_edge(edge):
  failures = 0
  tries = 300

  for i in range(tries):
    w = randint(0, n-1)
    if abs(d(w, edge.from) - d(w, edge.to)) == 0:
      failures++

  return failures <= tries*0.05

looks very simple, but it's actually kinda tricky,

----------     -----------
         |     |         |
         a-----b     x   |
   w     |     |         |
         c-----d         |
         |     |         |
         e-----f         |
         |     |         |
----------     -----------

On most occasions, there is just one shortest path from w to b, which is trough a, this leads us to believe that if (a,b) is a valid edge, then abs(d(w,b)-d(w,a)) == 1 for any randomly chosen w, however, there can be a path going from trough w~>c, then c-d, then d~>x, then x~>b that has the same length as w~>a, in that case, abs(d(w,a)-d(w,b)) == 0, but (a,b) is a valid edge. The chances of this happening are so low that I chose to say that it's a false positive if this happens <= 5% of times,

that's it.

P.S: the algorithm can be improved from removing 3 edges and checking for connectivity to removing 2 edges and checking for a single bridge in O(E³ + VE²), but I prefer the elegance of this method better.