Nested map to sequence of tuples representing edges in Clojure

How might one go about expressing the following transformation in idiomatic Clojure?

(def m
     {:a {:b {:c nil
              :d nil}
          :e nil}})


(map->edges m) ; =>


([:a :b] [:b :c] [:b :d] [:e nil] [:d nil] [:a :e] [:e nil])

I don't care about the order in which vectors appear in the result, so either depth-first or breath-first search strategies are fine.