\(G\) の中で最も小さなサイズの閉路を1つとり、それに含まれる頂点の集合が求める答えです。

よって ABC191E Come Back Quickly (解説)と同じ問題を解けばよいです(ただし、復元付き)。ABC191Eと違いこの問題には辺に重みがないので、単一始点最短経路問題を解く部分でダイクストラ法のかわりに BFS を用いることにより、計算量は \(O(N(N+M))\) になります。

復元は、頂点対\((p,q)\) であって、 \(d(p,q)+d(q,p) = \min\{d(x,y)+d(y,x)\}\) かつ \(d(q,p)=1\) であるようなものを1つとり、\(p\) から \(q\) への最短経路(の1つ)に含まれる頂点を列挙すればよいです。そのような頂点たちは、\(d(p,x)+d(x,q)=d(p,q)\) かつ \(d(x,q)=1\) であるような頂点 \(x\) を1つ求め \(q\) に置き換える操作をしていくことで、\(q\) に近い側から \(1\) 頂点ずつ求めることができます。計算量は \(O(N^2+M)\) です。