ｸｲｽﾞ大陸

答えを見つけるだけなら大して難しくはないのです。
町の数がそれのときの自由度の最大値は簡単に分かります。
町の数が1個少ないときにはその自由度にできないことを示すのがちと面倒です。
あとは自分が納得できるかどうかですね。