START_TIME = Time.utc.to_unix_ms TL = 7500 INF = 1 << 28 RND = Random.new(2) macro debug(msg) {% if flag?(:local) %} STDERR.puts({{msg}}) {% end %} end main def main n, m = read_line.split.map(&.to_i) x, y, z = read_line.split.map { |i| i.to_i - 1 } g = Array.new(n) { [false] * n } m.times do a, b = read_line.split.map(&.to_i) g[a - 1][b - 1] = g[b - 1][a - 1] = true end puts solve(x, y, z, g, START_TIME + TL) end def solve(x, y, z, g, tl) n = g.size wait = (0...n).select { |i| ![x, y, z].includes?(i) } best_ans = INF ratio_pena = 1 score_pena = 3 ps = [x, y, z] cooler = 0.3 turn = 0 while true if (turn & 0xFFF) == 0 cur_time = Time.utc.to_unix_ms if cur_time > tl debug("turn: #{turn}") break end end pos = RND.rand(ps.size) if ps[pos] == x || ps[pos] == y || ps[pos] == z ope = 1 else ope = RND.rand(3) end np = pos == ps.size - 1 ? 0 : pos + 1 case ope when 0 # remove diff_pena = 0 diff_pena -= 1 if g[ps[pos]][ps[np]] diff_pena -= 1 if g[ps[pos]][ps[pos - 1]] diff_pena += 1 if g[ps[pos - 1]][ps[np]] diff = diff_pena * ratio_pena - 1 if accept(diff, cooler) score_pena += diff_pena wait << ps[pos] ps.delete_at(pos) if score_pena == 0 && ps.size < best_ans best_ans = ps.size end debug("remove #{score_pena} #{ps.size} #{turn}") debug("#{ps}") end when 1 # insert next if wait.empty? ip = RND.rand(wait.size) ins = wait[ip] diff_pena = 0 diff_pena -= 1 if g[ps[pos]][ps[np]] diff_pena += 1 if g[ins][ps[np]] diff_pena += 1 if g[ins][ps[pos]] diff = diff_pena * ratio_pena + 1 if accept(diff, cooler) score_pena += diff_pena wait[ip], wait[-1] = wait[-1], wait[ip] wait.pop ps.insert(pos + 1, ins) if score_pena == 0 && ps.size < best_ans best_ans = ps.size end debug("insert #{score_pena} #{ps.size} #{turn}") debug("#{ps}") end when 2 # swap next if wait.empty? ip = RND.rand(wait.size) ins = wait[ip] diff_pena = 0 diff_pena -= 1 if g[ps[pos]][ps[np]] diff_pena -= 1 if g[ps[pos]][ps[pos - 1]] diff_pena += 1 if g[ins][ps[np]] diff_pena += 1 if g[ins][ps[pos - 1]] diff = diff_pena * ratio_pena if accept(diff, cooler) score_pena += diff_pena wait[ip] = ps[pos] ps[pos] = ins if score_pena == 0 && ps.size < best_ans best_ans = ps.size end debug("swap #{score_pena} #{ps.size} #{turn}") debug("#{ps}") end end turn += 1 end return best_ans == INF ? -1 : best_ans end def accept(diff, cooler) return true if diff <= 0 v = -diff * cooler return RND.rand < Math.exp(v) end