実は与えられるグラフが木の場合によい書き込み方が存在します。 よって、適当な全域木を一つ選んでその木に対するよい書き込み方を求めればよいです。以下はよい書き込み方を求めるアルゴリズムの例です。

選んだ木を根付き木として根から数を書き込んでいきます。 根に \(1\) を書き込み、根に近い順に頂点に順番に数を書き込んでいきます。すると、ある頂点 \(u\) に数を書き込むタイミングで \(u\) の親 \(p\) には必ず数が書き込まれています。頂点 \(p\) に書き込まれの値が辺のラベルと等しいならそれ以外の数を、異なるなら辺のラベルの値を \(u\) に書き込めばよいです。

これは \(O(N+M)\) で実行可能で十分高速です。