aとbしかないので結構できそうな雰囲気を感じる。
- Mが奇数の時
fig.1の(i)、(ii)のいずれであっても、2頂点を往復すれば、回文になる。
よって常に可能。
a <-> aなら aaa...
a <-> b なら abababa...
- Mが偶数の時
(i)の場合往復で可能
a <-> a なら aaaaa....
N=2かつ(ii)のときは回分にできないので不可能
問題はそれ以外の時だけど、(iii)がみつかれば、
abba abba abba ...
と回文がつくれる。また回文の先頭と末尾を消しても回文なので、偶数長の回文を3頂点の往復でつくることができる。
で、3頂点以上あれば(iii)は（たぶん）常に含まれる。
証明はわからないが、3頂点での辺は6しかないので全探索してたしかめれば、(i)か(iii)のいずれかのパターンになると思われる。
あとは実装の問題。
(iii)は3重ループまわして見つかったらブレイクで良い思う。
上の説がただしいなら任意の3頂点を探索するだけでも、(iii)をみたす辺の集合が見つかると思う。
この方法でAC。
場合分けが複数あるので"YES"の出力し忘れでWAに悩んだ。
