It turns out there is always a solution for a tree. Thus, we just need to randomly choose some spanning tree of the graph and consider only that tree. Below is one possible algorithm to find a good way of writing integers on a tree.

Let us make the tree rooted and write integers from the root to the bottom. We first write \(1\) on the root, then write numbers on the vertices just beneath the root, and so on. When we write a number on some vertex \(u\), the parent \(p\) of \(u\) already has a number written. If the number on \(p\) equals the label of the edge, we write some other number; otherwise, we write the number that is the label of the edge.

It can work in \(O(N+M)\) time, and it is fast enough.