AGC013 Hamiltonish Path - 足跡-sokuseki-

問題概要

$N$ 頂点 $M$ 辺の、連結な単純無向グラフが与えられる。頂点には $1$ から $N$ までの番号がついており、辺には $1$ から $M$ までの番号がついている。辺 $i$ は、頂点 $A_i$ と頂点 $B _i$ を結んでいる。次の条件を満たすパスを $1$ つ見つけて出力する（あり得る答えのうちどれを出力しても良い）。

2個以上の頂点を通る
同じ頂点を2度以上通らない
パスの少なくとも一方の端点と直接辺で結ばれている頂点は必ずパスに含まれる

制約
$2 \le N \le 10^5$
$1 \le M \le 10^5$
$1 \le A_i < B_i \le N$

解法

条件3の「パスの少なくとも一方の端点と直接辺で結ばれている頂点は必ずパスに含まれる」が具体的にどういうことかについて考えてみる。
パスの少なくとも一方の端点と直接辺で結ばれている頂点がパスに含まれていないという状態は、パスの端点からその頂点に対して、パスを伸ばすことができるということを意味する。つまり、条件3が言いたいことは、あるパスがあったときに、条件2を満たした上で、そのパスをできるだけ長く伸ばしたものを出力しないといけないということ。

よって解法の方針は