オイラー路の構築（無向グラフ） (paizaランク A 相当)

グラフ上の任意の頂点から出発して、すべての辺を使って一筆書きをすることができるようなグラフを準オイラーグラフと呼びます。また、そのような一筆書きの順番で頂点を並べたパスをオイラー路と呼びます。ただし、始点と終点が同じ頂点である必要はありません。

n 頂点 m 辺の無向グラフが与えられます。i 番目の辺は頂点 a_i と頂点 b_i を結んでいます。なお、グラフは自己ループや多重辺を含む場合があります。

このグラフは準オイラーグラフになっています。そこで、このグラフのオイラー路を構築してください。
以下の方針や擬似コードも参考にしてください。

・ 方針
今見ている頂点から、「行き止まりになるまで進み続けて、通った頂点を戻りながらパスに追加していく」ということを辺がなくなるまで繰り返す。

・ 擬似コード
main 関数内でのグラフの受け取りの方法を以下のように変更してみましょう。

// 無向グラフの場合、隣接リスト g に辺が 2 本ずつ追加されるため、ある辺を使用したときに、逆向きの辺を使用済みにする必要がある
// そこで、入力を受け取って無向グラフの隣接リスト g を構築するときに、逆向きの辺のインデックスも記録しておく
// つまり、(頂点番号, 逆向きの辺のインデックス) の組を要素とする隣接リストになる
for i = 1 から m まで:
    a_i, b_i を受け取る
    len_ga = 配列 g[a_i] の長さ   // g[a_i] の次のインデックス
    len_gb = 配列 g[b_i] の長さ   // g[b_i] の次のインデックス
    g[a_i] に組 (b_i, len_gb) を追加
    g[b_i] に組 (a_i, len_ga) を追加

また、以下の関数を定義し、main 関数内で用いることで実装を完成させましょう。

// 隣接リスト g を用いて動的配列 path に頂点を追加していく関数
dfs(v, g, path):
    while g[v] が空でない:
        (u, rev) = g[v] の末尾の要素
        g[v] の末尾の要素を削除

        if u が -1 でない:
            g[u][rev] の 1 番目の要素 (頂点番号) を -1 にする    // 逆向きの辺を使用済みにする
            dfs(u, g, path)

    path に v を追加

// オイラー路を構築する関数
construct_eulerian_path(g, path):
    // 次数が奇数の頂点を探し、なければ最初の頂点を始点とする
    start = 0
    for v = 1 から n まで:
        if 配列 g[v] の長さが奇数:
            start = v
            break

    // オイラー路を構築する
    動的配列 path を空で初期化
    dfs(start, g, path)
    path を逆順にする    // 頂点が逆順に追加されるので元に戻す
    return path