Approach 焼きなまし法を使いました。去年の中尾さん高速化をまねしました。
  • 回転させたときに、頂点推移的なグラフだけ使う。(ASPLの計算するときに、すべての頂点から幅優先探索をしなくてよくなる。例えば、180度回転させて同じ形なら、2つのグループに分けれて、幅優先探索する頂点は半分になります。)
  • 並列化して、複数の幅優先探索を同時にやる。
    • やったけど、自分のコンピュータでは高速化の効果は出なかったような...。
  • 1つの幅優先探索を、並列化してやる。
    • やってない。
  • スーパーコンピュータを使う。
    • 使ってない。お休みしてたと思います。


 去年はGrid Graph で Nakano さんとスコアに差があったけど、今年のアプローチでやってみたら、ほとんど同じスコアが出た。
 radeyeさんは、去年の General Graph の 72node 4degree を山登りで最適解出しててさすがだな~と思った。私は去年、焼きなましで結構頑張ったけど最適解だせなくて、今年のアプローチだと一瞬で出て「本当か」ってなった。もしかしたら、内径が大きいほうが良いばあいは存在しません。の例外かな。
 最初圧勝だったけど、最後にほとんど全部逆転されて受賞しなかった。去年できなかったことを今年できるようになってたし、去年はgraph を借りたけど今年は貸せたし、逆転されても僅差だったので、今年のほうが手応えはありました。

追記(10月23日)
 General Graph でグループ数が多いときは、下のコードの IGraph の実装は、全部の頂点を持つ必要がなくて、メモリを節約できたのが楽しかったかも?
 後はこれ、グレタ・トゥーンベリさん(職業 環境少女)ごめんよ。焼きなまし法みたいな時間のかかるアルゴリズムを並列で長時間実行して、ちょっと温暖化させたかも。パソコンから出てくる空気が火傷するかと思うほど熱かったからね。


source code(twitter の gif アニメで使ったやつ)
実行は
Main.main(("thread 1 group 4 graph 3 timelimit 60 print swap swap1 startRate 0.1 endRate 0.1 useMean true useMax false useExp 1").split(" "));
だけど、100万回iteration したら終わりになってるので、timelimitは意味ないね。
import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.RenderingHints;
import java.awt.image.BufferedImage;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.UnsupportedEncodingException;
import java.nio.charset.Charset;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;

import javax.imageio.IIOImage;
import javax.imageio.ImageIO;
import javax.imageio.ImageWriter;
import javax.imageio.stream.ImageOutputStream;

public class Main {
    private int R;
    private int C;
    private int length;
    private int degree;
    public static final int[] gridR = { 5, 5, 10, 10, 10, 20, 20, 20, 100, 100, 100, 32, };
    public static final int[] gridC = { 5, 10, 10, 10, 10, 20, 20, 20, 100, 100, 100, 32, };
    public static final int[] degrees = { 4, 4, 4, 6, 8, 4, 6, 8, 4, 6, 8, 4, };
    public static final int[] lengthes = { 2, 2, 2, 3, 4, 2, 3, 4, 2, 3, 4, 3, };

    private Graph graph;
    private Graph bestGraph;
    private Graph tmpGraph;

    private int diam;
    private int bestDiam;

    private double aspl;
    private double bestAspl;

    private int invalid;

    static final XorShift rng = new XorShift(System.nanoTime());
    static final Watch watch = new Watch();
    private SAState sa = new SAState();

    private ArrayList<Integer> dr;
    private ArrayList<Integer> dc;

    private IntQueue queue;
    private boolean[] used;
    private boolean[] usedGroup;

    private int numGroups;
    private int numVertexes;
    private int numCenters;

    private int timelimit;
    private boolean useTimer;
    private boolean print;
    private boolean useSwap1;
    private boolean useSwap2;
    private static final TimerManager timer = new TimerManager();

    public static void main(String[] args) {
        Main m = new Main();
        for (int i = 0; i < args.length; i++) {
            if (args[i].equals("thread")) {
                m.numThreads = Integer.parseInt(args[++i]);
            } else if (args[i].equals("group")) {
                m.numGroups = Integer.parseInt(args[++i]);
            } else if (args[i].equals("graph")) {
                int j = Integer.parseInt(args[++i]);
                m.R = m.gridR[j];
                m.C = m.gridC[j];
                m.degree = m.degrees[j];
                m.length = m.lengthes[j];
            } else if (args[i].equals("timelimit")) {
                m.timelimit = Integer.parseInt(args[++i]);
            } else if (args[i].equals("timer")) {
                m.useTimer = true;
            } else if (args[i].equals("print")) {
                m.print = true;
            } else if (args[i].equals("swap")) {
                m.useSwap1 = true;
            } else if (args[i].equals("swap1")) {
                m.useSwap2 = true;
            } else if (args[i].equals("startRate")) {
                m.sa.startRate = Double.parseDouble(args[++i]);
            } else if (args[i].equals("endRate")) {
                m.sa.endRate = Double.parseDouble(args[++i]);
            } else if (args[i].equals("useExp")) {
                m.sa.useExp = Boolean.parseBoolean(args[++i]);
            } else if (args[i].equals("useMean")) {
                m.sa.useMean = Boolean.parseBoolean(args[++i]);
            } else if (args[i].equals("useMax")) {
                m.sa.useMax = Boolean.parseBoolean(args[++i]);
            }
        }
        m.runAGraph();
        if (m.print)
            timer.print();
    }

    private void runAGraph() {
        numVertexes = (R * C) / numGroups;
        numCenters = (R * C) - (numGroups * numVertexes);

        double[] lower_bound_of_diam_aspl = Function.lower_bound_of_diam_aspl(R * C, degree);
        Utils.debug();
        Utils.debug(R + "x" + C, "degree", degree, "length", length, "numGroups", numGroups, "numVertexes", numVertexes, "numCenters", numCenters, "diam", (int) lower_bound_of_diam_aspl[0], "aspl", lower_bound_of_diam_aspl[1]);

        init();
        bestDiam = (int) 1e9;
        bestAspl = 1e9;

        boolean useGreedy = true;
        if (!useGreedy) {
            readSolution();
        }
        if (useGreedy) {
            boolean ok = false;
            if (bestDiam < 1e8 && calculateNumGroups(graph) == numGroups) {
                ok = true;
            }
            if (!ok) {
                clearGraph();
                for (int challenge = 0; challenge < 1e2; challenge++) {
                    if (createRandomGridGraph(numGroups)) {
                        ok = true;
                        break;
                    }
                }
                if (ok) {
                    if (!checkDegree()) {
                        ok = false;
                    }
                    if (calculateNumGroups(graph) != numGroups) {
                        ok = false;
                    }
                }
                if (!ok) {
                    if (print)
                        Utils.debug("fail createRandomGridGraph");
                    return;
                }
            }
        }
        watch.init();
        calculateScore(graph, 1, 1);
        Utils.debug(invalid, diam, aspl, "group", 1, "thread", 1, "time", watch.getSecondString());
        saveBest(false);

        watch.init();
        calculateScore(graph, calculateNumGroups(graph), 1);
        if (print)
            Utils.debug(invalid, diam, aspl, "group", calculateNumGroups(graph), "thread", 1, "time", watch.getSecondString());
        saveBest(false);

        watch.init();
        calculateScore(graph, 1, numThreads);
        if (print)
            Utils.debug(invalid, diam, aspl, "group", 1, "thread", numThreads, "time", watch.getSecondString());
        saveBest(false);

        watch.init();
        calculateScore(graph, calculateNumGroups(graph), numThreads);
        if (print)
            Utils.debug(invalid, diam, aspl, "group", calculateNumGroups(graph), "thread", numThreads, "time", watch.getSecondString());
        saveBest(false);

        loadBest();
        if (R * C < 2000) {
            calculateScore(graph, 1, numThreads);
        } else {
            calculateScore(graph, calculateNumGroups(graph), numThreads);
        }
        if (print)
            Utils.debug(bestDiam, bestAspl);
        if (bestDiam > 1e8) {
            return;
        }
        printDegree();

        watch.init();
        sa.startTime = 0;
        sa.endTime = 1e6;
        for (int j = 0; j < 10; j++) {
            view();
        }
        SA();

        for (int j = 0; j < 20; j++) {
            view();
        }
        Utils.debug("diff diam", bestDiam - lower_bound_of_diam_aspl[0], "diff aspl", bestAspl - lower_bound_of_diam_aspl[1]);

        writeSolution();

        gifWriter.close();

    }

    private int calculateNumGroups(IGraph graph2) {
        if (useTimer)
            timer.start("calculateNumGroups");
        group4: if (R == C) {
            for (int r = 0; r < R; r++) {
                for (int c = 0; c < C; c++) {
                    int node = z(r, c);
                    for (int i = 0; i < graph.degree(node); i++) {
                        int node2 = graph.getNode(node, i);
                        for (int group = 0; group < 4; group++) {
                            int rnode = rotate90(node, group);
                            int rnode2 = rotate90(node2, group);
                            if (!graph.hasEdge(rnode, rnode2)) {
                                break group4;
                            }
                        }
                    }
                }
            }
            if (useTimer)
                timer.stop("calculateNumGroups");
            return 4;
        }
        group2: {
            for (int r = 0; r < R; r++) {
                for (int c = 0; c < C; c++) {
                    int node = z(r, c);
                    for (int i = 0; i < graph.degree(node); i++) {
                        int node2 = graph.getNode(node, i);
                        for (int group = 0; group < 2; group++) {
                            int rnode = rotate180(node, group);
                            int rnode2 = rotate180(node2, group);
                            if (!graph.hasEdge(rnode, rnode2)) {
                                break group2;
                            }
                        }
                    }
                }
            }
            if (useTimer)
                timer.stop("calculateNumGroups");
            return 2;
        }
        if (useTimer)
            timer.stop("calculateNumGroups");
        return 1;
    }

    private boolean createRandomGridGraph(int numGroups) {
        if (useTimer)
            timer.start("createRandomGridGraph");
        graph.clearEdges();
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                int node = z(r, c);
                if (graph.degree(node) > degree) {
                    if (useTimer)
                        timer.stop("createRandomGridGraph");
                    return false;
                }
                if (graph.degree(node) == degree) {
                    continue;
                }
                for (int challenge2 = 0; challenge2 < 10 * degree; challenge2++) {
                    if (graph.degree(node) > degree) {
                        if (useTimer)
                            timer.stop("createRandomGridGraph");
                        return false;
                    }
                    if (graph.degree(node) == degree) {
                        break;
                    }

                    int d = (int) (dr.size() * rng.nextDouble());
                    int nr = r + dr.get(d).intValue();
                    int nc = c + dc.get(d).intValue();
                    if (nr < 0 || nr >= R || nc < 0 || nc >= C) {
                        challenge2--;
                        continue;
                    }
                    int nnode = z(nr, nc);
                    if (graph.hasEdge(node, nnode) || graph.degree(nnode) >= degree) {
                        continue;
                    }
                    if (numGroups == 1) {
                        graph.addEdge(node, nnode);
                    } else if (numGroups == 2) {
                        for (int g = 0; g < numGroups; g++) {
                            int rotate = rotate180(node, g);
                            int nrotate = rotate180(nnode, g);
                            graph.addEdge(rotate, nrotate);
                        }
                    } else if (numGroups == 4) {
                        for (int g = 0; g < numGroups; g++) {
                            int rotate0 = rotate90(node, g);
                            int nrotate0 = rotate90(nnode, g);
                            graph.addEdge(rotate0, nrotate0);
                        }
                    }
                }

                if (graph.degree(node) < degree) {
                    if (useTimer)
                        timer.stop("createRandomGridGraph");
                    return false;
                }

            }
        }

        if (useTimer)
            timer.stop("createRandomGridGraph");
        return true;
    }

    private void writeSolution() {
        if (useTimer)
            timer.start("writeSolution");
        StringBuilder sb = new StringBuilder();
        for (int from = 0; from < R * C; from++) {
            for (int j = 0; j < graph.degree(from); j++) {
                int to = graph.getNode(from, j);
                if (from < to) {
                    sb.append((r(from) + "," + c(from)) + " " + (r(to) + "," + c(to)) + "\n");
                }
            }
        }
        TextFileIO.write(sb.toString(), Paths.get("./out/grid_" + (R + "_x_" + C) + "_d_" + degree + "_l_" + length + "_diam_" + diam + "_aspl_" + aspl + "_g_" + numGroups + "_.edges"));
        if (useTimer)
            timer.stop("writeSolution");
    }

    private void readSolution() {
        if (useTimer)
            timer.start("readSolution");
        File outDir = Paths.get("./out/").toFile();
        ArrayList<File> files = new ArrayList<>();
        for (File file : outDir.listFiles()) {
            files.add(file);
        }
        Collections.shuffle(files);
        for (File file : files) {
            if (!file.isFile()) {
                Utils.debug("continue !file.isFile()");
                continue;
            }
            String name = file.getName();
            String[] split = name.split("_");
            if (split.length != 15) {
                continue;
            }
            if (split[0].equals("grid") && split[2].equals("x") && split[4].equals("d") && split[6].equals("l") && split[8].equals("diam") && split[10].equals("aspl") && split[12].equals("g")) {
            } else {
                continue;
            }
            int r = Integer.parseInt(split[1]);
            int c = Integer.parseInt(split[3]);
            int d = Integer.parseInt(split[5]);
            int l = Integer.parseInt(split[7]);
            int g = Integer.parseInt(split[13]);
            boolean useMod = !true;
            if (r == this.R && c == this.C && d == this.degree && l == this.length && (useMod ? g % this.numGroups == 0 : g == this.numGroups)) {
            } else {
                continue;
            }
            clearGraph();
            for (String line : TextFileIO.readLines(file.toPath(), StandardCharsets.UTF_8)) {
                String[] split2 = line.split("[, ]");
                int fromR = Integer.parseInt(split2[0]);
                int fromC = Integer.parseInt(split2[1]);
                int toR = Integer.parseInt(split2[2]);
                int toC = Integer.parseInt(split2[3]);
                int from = z(fromR, fromC);
                int to = z(toR, toC);
                addEdge(from, to);
            }
            if (R * C < 2000) {
                calculateScore(graph, 1, 1);
            } else {
                calculateScore(graph, calculateNumGroups(graph), 1);
            }
            saveBest(false);
            if (!useMod) {
                if (invalid > 0 || diam > bestDiam || (diam == bestDiam && aspl > bestAspl)) {
                    file.delete();
                }
            }
            loadBest();
            if (R * C < 2000) {
                calculateScore(graph, 1, 1);
            } else {
                calculateScore(graph, calculateNumGroups(graph), 1);
            }
        }

        if (useTimer)
            timer.stop("readSolution");
    }

    private void clearGraph() {
        graph.clearEdges();
    }

    private void init() {

        graph = new Graph(R * C);
        bestGraph = new Graph(R * C);
        tmpGraph = new Graph(R * C);

        this.dr = new ArrayList<>();
        this.dc = new ArrayList<>();
        for (int dr = -length; dr <= length; dr++) {
            int l = length - Math.abs(dr);
            for (int dc = -l; dc <= l; dc++) {
                if (dr == 0 && dc == 0) {
                    continue;
                }
                this.dr.add(dr);
                this.dc.add(dc);
            }
        }

        usedGroup = new boolean[R * C];
        used = new boolean[R * C];
        queue = new IntQueue(R * C + 2);
        maxs = new int[numThreads];
        sums = new double[numThreads];
        invalids = new int[numThreads];
        useds = new boolean[numThreads][R * C];
        queues = new IntQueue[numThreads];
        for (int i = 0; i < numThreads; i++) {
            queues[i] = new IntQueue(R * C + 2);
        }
    }

    private void SA() {
        double second = Math.ceil(watch.getSecond());
        sa.init();
        for (;; sa.numIterations++) {
            if ((sa.numIterations & ((1 << 0) - 1)) == 0) {
                sa.update();
                if (sa.isTLE() || sa.numIterations > 1e5 + sa.lastAcceptIterations) {
                    TextFileIO.appendln(Utils.toString("grid_" + R + "x" + C + "_d_" + degree + "_g_" + numGroups + "_t_" + numThreads + "_sw_" + ((useSwap1 ? 1 : 0) + (useSwap2 ? 2 : 0)) + "_diam_" + (diam) + "_aspl_" + (aspl) + "_i_" + sa.numIterations + "_" + (int) (watch.getSecond()) + "/" + (int) (sa.endTime - sa.startTime + 0.9), getClass().getName()));
                    loadBest();
                    Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%2d", diam), String.format("%7.5f", aspl), String.format("%2d", bestDiam), String.format("%7.5f", bestAspl), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature), sa.startTemperature, sa.endTemperature, R + "x" + C + "_d_" + degree + "_l_" + length + "_g_" + numGroups + "_t_" + numThreads + "_sw_" + ((useSwap1 ? 1 : 0) + (useSwap2 ? 2 : 0)) + "_i_" + sa.numIterations + "_" + (int) (sa.time - sa.startTime + 0.5) + "/" + (int) (sa.endTime - sa.startTime + 0.5));
                    break;
                }
                if (print)
                    if (watch.getSecond() > second) {
                        second++;
                        Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%2d", diam), String.format("%7.5f", aspl), String.format("%2d", bestDiam), String.format("%7.5f", bestAspl), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature), sa.startTemperature, sa.endTemperature, R + "x" + C + "_d_" + degree + "_l_" + length + "_g_" + numGroups + "_t_" + numThreads + "_sw_" + ((useSwap1 ? 1 : 0) + (useSwap2 ? 2 : 0)) + "_i_" + sa.numIterations + "_" + (int) (sa.time - sa.startTime + 0.5) + "/" + (int) (sa.endTime - sa.startTime + 0.5));
                    }

            }

            mutate();
        }
        Utils.debug("SA", "time", watch.getSecondString());
    }

    private void mutate() {
        if (useSwap1) {
            if (useSwap2) {
                double random = 2 * rng.nextDouble();
                if (random < 1) {
                    swap2();
                } else if (random < 2) {
                    swapNextAndNextNext2();
                }
            } else {
                swap2();
            }
        } else {
            if (useSwap2) {
                swapNextAndNextNext2();
            } else {
                throw new AssertionError();
            }
        }
    }

    private ArrayList<int[]> list = new ArrayList<>();

    private void swapNextAndNextNext2() {
        if (useTimer)
            timer.start("swapNextAndNextNext2");
        list.clear();
        int node0 = (int) (R * C * rng.nextDouble());
        for (int i1 = 0; i1 < graph.degree(node0); i1++) {
            int node1 = graph.getNode(node0, i1);
            assert node1 != node0;
            for (int i2 = 0; i2 < graph.degree(node1); i2++) {
                int node2 = graph.getNode(node1, i2);
                if (node2 == node0 || node2 == node1) {
                    continue;
                }
                if (graph.hasEdge(node0, node2) || graph.hasEdge(node2, node0)) {
                    continue;
                }
                if (length(node0, node2) > length) {
                    continue;
                }
                for (int i3 = 0; i3 < graph.degree(node2); i3++) {
                    int node3 = graph.getNode(node2, i3);
                    if (node3 == node0 || node3 == node1 || node3 == node2) {
                        continue;
                    }
                    if (graph.hasEdge(node1, node3) || graph.hasEdge(node3, node1)) {
                        continue;
                    }
                    if (length(node1, node3) > length) {
                        continue;
                    }
                    list.add(new int[] { node1, node2, node3 });
                }
            }
        }

        if (list.size() == 0) {
            if (useTimer)
                timer.stop("swapNextAndNextNext2");
            return;
        }
        int index = (int) (list.size() * rng.nextDouble());
        int[] nodes = list.get(index);
        int node1 = nodes[0];
        int node2 = nodes[1];
        int node3 = nodes[2];

        saveCurrentGraph();

        if (numGroups == 4) {
            for (int group = 0; group < numGroups; group++) {
                int rotate = group;
                removeEdge(rotate90(node0, rotate), rotate90(node1, rotate));
                removeEdge(rotate90(node2, rotate), rotate90(node3, rotate));
                addEdge(rotate90(node0, rotate), rotate90(node2, rotate));
                addEdge(rotate90(node1, rotate), rotate90(node3, rotate));
            }
        } else if (numGroups == 2 || numGroups == 1) {
            for (int group = 0; group < numGroups; group++) {
                int rotate = group;
                removeEdge(rotate180(node0, rotate), rotate180(node1, rotate));
                removeEdge(rotate180(node2, rotate), rotate180(node3, rotate));
                addEdge(rotate180(node0, rotate), rotate180(node2, rotate));
                addEdge(rotate180(node1, rotate), rotate180(node3, rotate));
            }
        }

        if (!checkDegree() || calculateNumGroups(graph) != numGroups) {
            loadCurrentGraph();
            if (useTimer)
                timer.stop("swapNextAndNextNext2");
            return;
        }

        int currentDiam = diam;
        double currentAspl = aspl;
        int currentInvalid = invalid;
        calculateScore(graph, numGroups, numThreads);
        double deltaScore = (invalid + aspl) - (currentInvalid + currentAspl);

        if (sa.accept(deltaScore)) {
            saveBest();
        } else {
            diam = currentDiam;
            aspl = currentAspl;
            invalid = currentInvalid;
            if (numGroups == 4) {
                for (int group = 0; group < numGroups; group++) {
                    int rotate = group;
                    removeEdge(rotate90(node0, rotate), rotate90(node2, rotate));
                    removeEdge(rotate90(node1, rotate), rotate90(node3, rotate));
                    addEdge(rotate90(node0, rotate), rotate90(node1, rotate));
                    addEdge(rotate90(node2, rotate), rotate90(node3, rotate));
                }
            } else if (numGroups == 2 || numGroups == 1) {
                for (int group = 0; group < numGroups; group++) {
                    int rotate = group;
                    removeEdge(rotate180(node0, rotate), rotate180(node2, rotate));
                    removeEdge(rotate180(node1, rotate), rotate180(node3, rotate));
                    addEdge(rotate180(node0, rotate), rotate180(node1, rotate));
                    addEdge(rotate180(node2, rotate), rotate180(node3, rotate));
                }
            }
        }
        if (useTimer)
            timer.stop("swapNextAndNextNext2");
    }

    private void swap2() {
        if (useTimer)
            timer.start("swap2");
        list.clear();
        int node0 = (int) (R * C * rng.nextDouble());

        for (int d = 0; d < dr.size(); d++) {
            int nr = r(node0) + dr.get(d).intValue();
            int nc = c(node0) + dc.get(d).intValue();
            if (nr < 0 || nr >= R) {
                continue;
            }
            if (nc < 0 || nc >= C) {
                continue;
            }
            int node2 = z(nr, nc);
            if (node2 == node0) {
                continue;
            }
            if (graph.hasEdge(node0, node2) || graph.hasEdge(node2, node0)) {
                continue;
            }
            if (length(node0, node2) > length) {
                continue;
            }

            for (int i1 = 0; i1 < graph.degree(node0); i1++) {
                int node1 = graph.getNode(node0, i1);
                assert node1 != node0;
                if (node1 == node0 || node1 == node2) {
                    continue;
                }

                for (int i3 = 0; i3 < graph.degree(node2); i3++) {
                    int node3 = graph.getNode(node2, i3);
                    if (node3 == node0 || node3 == node1 || node3 == node2) {
                        continue;
                    }
                    if (graph.hasEdge(node1, node3) || graph.hasEdge(node3, node1)) {
                        continue;
                    }
                    if (length(node1, node3) > length) {
                        continue;
                    }
                    list.add(new int[] { node1, node2, node3 });
                }
            }
        }

        if (list.size() == 0) {
            if (useTimer)
                timer.stop("swap2");
            return;
        }
        int index = (int) (list.size() * rng.nextDouble());
        int[] nodes = list.get(index);
        int node1 = nodes[0];
        int node2 = nodes[1];
        int node3 = nodes[2];
        saveCurrentGraph();

        if (numGroups == 4) {
            for (int group = 0; group < numGroups; group++) {
                int rotate = group;
                removeEdge(rotate90(node0, rotate), rotate90(node1, rotate));
                removeEdge(rotate90(node2, rotate), rotate90(node3, rotate));
                addEdge(rotate90(node0, rotate), rotate90(node2, rotate));
                addEdge(rotate90(node1, rotate), rotate90(node3, rotate));
            }
        } else if (numGroups == 2 || numGroups == 1) {
            for (int group = 0; group < numGroups; group++) {
                int rotate = group;
                removeEdge(rotate180(node0, rotate), rotate180(node1, rotate));
                removeEdge(rotate180(node2, rotate), rotate180(node3, rotate));
                addEdge(rotate180(node0, rotate), rotate180(node2, rotate));
                addEdge(rotate180(node1, rotate), rotate180(node3, rotate));
            }
        }

        if (!checkDegree() || calculateNumGroups(graph) != numGroups) {
            loadCurrentGraph();
            if (useTimer)
                timer.stop("swap2");
            return;
        }

        int currentDiam = diam;
        double currentAspl = aspl;
        int currentInvalid = invalid;
        calculateScore(graph, numGroups, numThreads);
        double deltaScore = (invalid + aspl) - (currentInvalid + currentAspl);

        if (sa.accept(deltaScore)) {
            saveBest();
        } else {
            diam = currentDiam;
            aspl = currentAspl;
            invalid = currentInvalid;
            if (numGroups == 4) {
                for (int group = 0; group < numGroups; group++) {
                    int rotate = group;
                    removeEdge(rotate90(node0, rotate), rotate90(node2, rotate));
                    removeEdge(rotate90(node1, rotate), rotate90(node3, rotate));
                    addEdge(rotate90(node0, rotate), rotate90(node1, rotate));
                    addEdge(rotate90(node2, rotate), rotate90(node3, rotate));
                }
            } else if (numGroups == 2 || numGroups == 1) {
                for (int group = 0; group < numGroups; group++) {
                    int rotate = group;
                    removeEdge(rotate180(node0, rotate), rotate180(node2, rotate));
                    removeEdge(rotate180(node1, rotate), rotate180(node3, rotate));
                    addEdge(rotate180(node0, rotate), rotate180(node1, rotate));
                    addEdge(rotate180(node2, rotate), rotate180(node3, rotate));
                }
            }
        }
        if (useTimer)
            timer.stop("swap2");
    }

    private boolean checkDegree() {
        if (useTimer)
            timer.start("checkDegree");
        for (int i = 0; i < R * C; i++) {
            if (graph.degree(i) != degree) {
                if (useTimer)
                    timer.stop("checkDegree");
                return false;
            }
        }
        if (useTimer)
            timer.stop("checkDegree");
        return true;
    }

    private void saveCurrentGraph() {
        if (useTimer)
            timer.start("saveCurrentGraph");
        tmpGraph.copy(graph);
        if (useTimer)
            timer.stop("saveCurrentGraph");
    }

    private void loadCurrentGraph() {
        if (useTimer)
            timer.start("loadCurrentGraph");
        graph.copy(tmpGraph);
        if (useTimer)
            timer.stop("loadCurrentGraph");
    }

    private void calculateScore(IGraph graph, int numGroups, int numThreads) {
        if (numThreads == 1) {
            calculateScore(graph, numGroups);
        } else {
            calculateScoreMultiThreads(graph, numGroups);
        }
    }

    private void calculateScore(IGraph graph, int numGroups) {
        if (useTimer)
            timer.start("calculateScore");
        int RxC = R * C;
        queue.clear();
        Arrays.fill(used, false);
        Arrays.fill(usedGroup, false);

        aspl = 0;
        diam = 0;
        invalid = 0;

        for (int startNode = 0; startNode < RxC; startNode++) {
            if (usedGroup[startNode]) {
                continue;
            }
            int total = 1;
            usedGroup[startNode] = true;
            if (numGroups == 2) {
                if (!usedGroup[rotate180(startNode, 1)]) {
                    total++;
                    usedGroup[rotate180(startNode, 1)] = true;
                }
            } else if (numGroups == 4) {
                for (int rotate = 1; rotate < 4; rotate++) {
                    if (!usedGroup[rotate90(startNode, rotate)]) {
                        total++;
                        usedGroup[rotate90(startNode, rotate)] = true;
                    }
                }
            }

            queue.clear();
            Arrays.fill(used, false);
            {
                queue.add((0 << 16) | (startNode));
                used[startNode] = true;
            }
            for (; !queue.isEmpty();) {
                int v = queue.poll();
                int distance = (v >>> 16) & ((1 << 16) - 1);
                int currentNode = (v >>> 0) & ((1 << 16) - 1);

                diam = Math.max(diam, distance);
                aspl += total * distance;

                if (graph.degree(currentNode) > degree) {
                    invalid += graph.degree(currentNode) - degree;
                }

                for (int i = 0; i < graph.degree(currentNode); i++) {
                    int nextNode = graph.getNode(currentNode, i);
                    if (used[nextNode]) {
                        continue;
                    }

                    if (length(currentNode, nextNode) > length) {
                        invalid += length(currentNode, nextNode) - length;
                    }
                    if (length(currentNode, nextNode) == 0) {
                        invalid++;
                    }

                    used[nextNode] = true;
                    queue.add(((distance + 1) << 16) | (nextNode));
                }
            }

            for (int node = 0; node < RxC; node++) {
                if (!used[node]) {
                    invalid++;
                }
            }

        }
        aspl /= (RxC * RxC - RxC);
        if (useTimer)
            timer.stop("calculateScore");
    }

    private int numThreads;
    private int[] maxs;
    private double[] sums;
    private int[] invalids;
    private IntQueue[] queues;
    private boolean[][] useds;

    private void calculateScoreMultiThreads(IGraph graph, int numGroups) {
        if (useTimer)
            timer.start("calculateScoreMultiThreads");
        Arrays.fill(usedGroup, false);

        Thread[] threads = new Thread[numThreads];
        for (int t = 0; t < numThreads; t++) {
            final int ft = t;
            maxs[ft] = 0;
            sums[ft] = 0;
            invalids[ft] = 0;
            threads[t] = new Thread(new Runnable() {
                @Override
                public void run() {
                    for (int startNode = ft; startNode < R * C; startNode += numThreads) {
                        if (usedGroup[startNode]) {
                            continue;
                        }
                        int total = 1;
                        usedGroup[startNode] = true;
                        if (numGroups == 2) {
                            if (!usedGroup[rotate180(startNode, 1)]) {
                                total++;
                                usedGroup[rotate180(startNode, 1)] = true;
                            }
                        } else if (numGroups == 4) {
                            for (int rotate = 1; rotate < 4; rotate++) {
                                if (!usedGroup[rotate90(startNode, rotate)]) {
                                    total++;
                                    usedGroup[rotate90(startNode, rotate)] = true;
                                }
                            }
                        }

                        queues[ft].clear();
                        Arrays.fill(useds[ft], false);
                        {
                            queues[ft].add((0 << 16) | (startNode));
                            useds[ft][startNode] = true;
                        }
                        for (; !queues[ft].isEmpty();) {
                            int v = queues[ft].poll();
                            int distance = (v >>> 16) & ((1 << 16) - 1);
                            int currentNode = (v >>> 0) & ((1 << 16) - 1);

                            maxs[ft] = Math.max(maxs[ft], distance);
                            sums[ft] += total * distance;

                            if (graph.degree(currentNode) > degree) {
                                invalid += graph.degree(currentNode) - degree;
                            }

                            for (int i = 0; i < graph.degree(currentNode); i++) {
                                int nextNode = graph.getNode(currentNode, i);
                                if (useds[ft][nextNode]) {
                                    continue;
                                }

                                if (length(currentNode, nextNode) > length) {
                                    invalids[ft] += length(currentNode, nextNode) - length;
                                }
                                if (length(currentNode, nextNode) == 0) {
                                    invalids[ft]++;
                                }

                                useds[ft][nextNode] = true;
                                queues[ft].add(((distance + 1) << 16) | (nextNode));
                            }
                        }

                        for (int node = 0; node < R * C; node++) {
                            if (!useds[ft][node]) {
                                invalids[ft]++;
                            }
                        }

                    }
                }
            });
        }

        for (int t = 0; t < numThreads; t++) {
            threads[t].start();
        }
        for (int t = 0; t < numThreads; t++) {
            try {
                threads[t].join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

        aspl = 0;
        diam = 0;
        this.invalid = 0;
        for (int t = 0; t < numThreads; t++) {
            aspl += (double) sums[t] / (R * C * R * C - R * C);
            diam = Math.max(diam, maxs[t]);
            this.invalid += invalids[t];
        }

        if (useTimer)
            timer.stop("calculateScoreMultiThreads");
    }

    private void saveBest() {
        saveBest(true);
    }

    private void saveBest(boolean print) {
        if (useTimer)
            timer.start("saveBest");
        if (invalid > 0) {
            if (this.print)
                Utils.debug("invalid", invalid);
            if (useTimer)
                timer.stop("saveBest");
            return;
        }
        if (diam < bestDiam || (diam == bestDiam && aspl <= bestAspl)) {
            if (print) {
                if (diam < bestDiam || (diam == bestDiam && aspl < bestAspl)) {
                    TextFileIO.appendln(Utils.toString("grid_" + R + "x" + C + "_d_" + degree + "_g_" + numGroups + "_t_" + numThreads + "_sw_" + ((useSwap1 ? 1 : 0) + (useSwap2 ? 2 : 0)) + "_diam_" + (diam) + "_aspl_" + (aspl) + "_i_" + sa.numIterations + "_" + (int) (sa.time - sa.startTime + 0.5) + "/" + (int) (sa.endTime - sa.startTime + 0.5), getClass().getName()));
                }
            }
            bestDiam = diam;
            bestAspl = aspl;
            bestGraph.copy(graph);
            count = 0;
        }
        view();
        if (useTimer)
            timer.stop("saveBest");
    }

    private void loadBest() {
        if (useTimer)
            timer.start("loadBest");
        diam = bestDiam;
        aspl = bestAspl;
        graph.copy(bestGraph);
        if (useTimer)
            timer.stop("loadBest");
    }

    private void printDegree() {
        if (useTimer)
            timer.start("printDegree");
        if (print)
            for (int i = 0; i < R * C; i++) {
                if (graph.degree(i) != degree) {
                    Utils.debug("ac", sa.acceptIterations, "node", i, "degree", graph.degree(i), "max degree", degree);
                }
            }
        if (useTimer)
            timer.stop("printDegree");
    }

    private void addEdge(int node0, int node1) {
        graph.addEdge(node0, node1);
    }

    private void removeEdge(int node0, int node1) {
        graph.removeEdge(node0, node1);
    }

    private int rotate180(int node, int group) {
        if (group % 2 == 0) {
            return node;
        }
        int r = r(node);
        int c = c(node);
        return z(R - 1 - r, C - 1 - c);
    }

    private int rotate90(int node, int group) {
        assert R == C;
        int r = r(node);
        int c = c(node);
        for (int i = 0; i < group; i++) {
            int nr = R - 1 - c;
            int nc = r;
            r = nr;
            c = nc;
        }
        return z(r, c);
    }

    private int length(int z, int z2) {
        return Math.abs(r(z2) - r(z)) + Math.abs(c(z2) - c(z));
    }

    private int z(int r, int c) {
        return r * C + c;
    }

    private int r(int z) {
        return z / C;
    }

    private int c(int z) {
        return z % C;
    }

    private GifWriter gifWriter = new GifWriter("./out/anime.gif");

    private int max = 32;
    private int count = 0;

    private void view() {
        if (count >= max) {
            if (count == max) {
                max = Math.max(1, max / 2);
            }
//            count = 0;
            return;
        }
        count++;

        int height = 512;
        int width = 512;
        int height2 = 30 + height;
        int width2 = 30 + width;
        BufferedImage bi = new BufferedImage(width2, height2, BufferedImage.TYPE_INT_RGB);
        Graphics2D g2 = (Graphics2D) bi.getGraphics();
        g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
        g2.setColor(new Color(0xDDDDDD));
        g2.fillRect(0, 0, width2, height2);

        g2.setColor(Color.WHITE);
        g2.fillRect(15, 15, width, height);

        int sizeR = height / R;
        int sizeC = width / C;
        int[] rToSizeC2 = new int[sizeC];
        for (int i = 0; i < rToSizeC2.length; i++) {
            rToSizeC2[i] = sizeC / (i + 1);
        }

        for (int from = 0; from < R * C; from++) {
            for (int j = 0; j < graph.degree(from); j++) {
                int to = graph.getNode(from, j);
                if (from >= to) {
                    continue;
                }
                g2.setColor(Color.LIGHT_GRAY);
                g2.drawLine(15 + sizeC / 2 + sizeC * (from % C), 15 + sizeR / 2 + sizeR * (from / C), 15 + sizeC / 2 + sizeC * (to % C), 15 + sizeR / 2 + sizeR * (to / C));
            }
        }
        g2.setColor(Color.GREEN);
        for (int from = 0; from < R * C; from++) {
            g2.drawOval(15 + sizeC / 2 + sizeC * (from % C) - 2, 15 + sizeR / 2 + sizeR * (from / C) - 2, 4, 4);
            g2.fillOval(15 + sizeC / 2 + sizeC * (from % C) - 2, 15 + sizeR / 2 + sizeR * (from / C) - 2, 4, 4);
        }

        int x = 30;
        int y = 30;

        g2.setColor(Color.BLACK);
        g2.drawString("Diam : " + diam, x, y += 15);
        g2.drawString("ASPL : " + aspl, x, y += 15);

        gifWriter.add(bi);

    }
}

class SAState {

    public static final boolean useTime = !true;

    public double startTime = 0;
    public double endTime = 1e6;
    public double time = startTime;

    public double startTemperature = 40;
    public double endTemperature = 1e9;
    public double expTemperature = 1;
    public double inverseTemperature = 1.0 / startTemperature;
    public double lastAcceptTemperature = startTemperature;

    public double startRange = 101;
    public double endRange = 3;
    public double range = startRange;

    public int numIterations;
    public int validIterations;
    public int acceptIterations;
    public int lastAcceptIterations;

    private double minAbsDeltaScore;
    private double maxAbsDeltaScore;
    private MeanHelper helper = new MeanHelper();

    public void init() {
        numIterations = 0;
        validIterations = 0;
        acceptIterations = 0;

        minAbsDeltaScore = 1e99;
        maxAbsDeltaScore = 1e-99;
        helper.clear();

        startTime = useTime ? Main.watch.getSecond() : numIterations;

        update();
        lastAcceptTemperature = inverseTemperature;
    }

    public void update() {
        updateTime();
        updateTemperature();
        updateRange();
    }

    public boolean useMean = true;
    public boolean useMax = !true;
    public double startRate = 0.5;
    public double endRate = 0.1;
    public boolean useExp = true;

    public void updateStartTemperature() {
        if (useMean) {
            double d = helper.mean(maxAbsDeltaScore);
            d = d > 0 ? d : maxAbsDeltaScore;
            startTemperature = (-1.0 * d) / Math.log(startRate);
        } else if (useMax) {
            startTemperature = (-1.0 * maxAbsDeltaScore) / Math.log(startRate);
        } else {
            startTemperature = (-1.0 * minAbsDeltaScore) / Math.log(startRate);
        }
    }

    public void updateEndTemperature() {
        endTemperature = (-1.0 * minAbsDeltaScore) / Math.log(endRate);
    }

    public void updateTemperature() {
        updateStartTemperature();
        updateEndTemperature();
        if (useExp) {
            double time0to1 = elapsedPercentage(startTime, endTime, time);
            double startY = startTemperature;
            double endY = endTemperature;
            double startX = Math.log(startY);
            double endX = Math.log(endY);
            double xStartToEnd = interpolate(startX, endX, time0to1);
            double temperature = Math.exp(xStartToEnd);

            inverseTemperature = 1.0 / temperature;
        } else {
            double time0to1 = elapsedPercentage(startTime, endTime, time);
            double startY = startTemperature;
            double endY = endTemperature;
            double temperature = interpolate(startY, endY, time0to1);

            inverseTemperature = 1.0 / temperature;
        }
    }

    public void updateRange() {
    }

    public void updateTime() {
        time = useTime ? Main.watch.getSecond() : numIterations;
    }

    private double elapsedPercentage(double min, double max, double v) {
        return (v - min) / (max - min);
    }

    private double interpolate(double v0, double v1, double d0to1) {
        return v0 + (v1 - v0) * d0to1;
    }

    public boolean isTLE() {
        return time >= endTime;
    }

    public boolean accept(double deltaScore) {
        double abs = Math.abs(deltaScore);
        if (abs > 1e-9) {
            helper.add(deltaScore);
            minAbsDeltaScore = Math.min(minAbsDeltaScore, abs);
            maxAbsDeltaScore = Math.max(maxAbsDeltaScore, abs);
        }
        return acceptS(deltaScore);
    }

    public boolean acceptB(double deltaScore) {
        validIterations++;
        if (deltaScore > -1e-9) {
            acceptIterations++;
            lastAcceptIterations = numIterations;
            return true;
        }

        assert deltaScore < 0;
        assert 1.0 / inverseTemperature >= 0;

        if (deltaScore * inverseTemperature < -10) {
            return false;
        }

        if (Main.rng.nextDouble() < Math.exp(deltaScore * inverseTemperature)) {
            acceptIterations++;
            lastAcceptTemperature = inverseTemperature;
            lastAcceptIterations = numIterations;
            return true;
        }
        return false;
    }

    public boolean acceptS(double deltaScore) {
        validIterations++;
        if (deltaScore < 1e-9) {
            acceptIterations++;
            lastAcceptIterations = numIterations;
            return true;
        }
        if (-deltaScore * inverseTemperature < -10) {
            return false;
        }
        if (Main.rng.nextDouble() < Math.exp(-deltaScore * inverseTemperature)) {
            acceptIterations++;
            lastAcceptTemperature = inverseTemperature;
            lastAcceptIterations = numIterations;
            return true;
        }
        return false;
    }

}

final class Utils {
    private Utils() {
    }

    public static final void debug(Object... o) {
        System.err.println(toString(o));
    }

    public static final String toString(Object... o) {
        return Arrays.deepToString(o);
    }

}

class Watch {
    private long start;

    public Watch() {
        init();
    }

    public double getSecond() {
        return (System.nanoTime() - start) * 1e-9;
    }

    public void init() {
        init(System.nanoTime());
    }

    private void init(long start) {
        this.start = start;
    }

    public String getSecondString() {
        return toString(getSecond());
    }

    public static final String toString(double second) {
        if (second < 60) {
            return String.format("%5.2fs", second);
        } else if (second < 60 * 60) {
            int minute = (int) (second / 60);
            return String.format("%2dm%2ds", minute, (int) (second % 60));
        } else {
            int hour = (int) (second / (60 * 60));
            int minute = (int) (second / 60);
            return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));
        }
    }

}

class XorShift {
    private int w = 88675123;
    private int x = 123456789;
    private int y = 362436069;
    private int z = 521288629;

    public XorShift(long l) {
        x = (int) l;
    }

    public int nextInt() {
        final int t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));
        return w;
    }

    public long nextLong() {
        return ((long) nextInt() << 32) ^ (long) nextInt();
    }

    public double nextDouble() {
        return (nextInt() >>> 1) * 4.6566128730773926E-10;
    }

    public int nextInt(int n) {
        return (int) (n * nextDouble());
    }

}

class UnionFind {
    private int[] par;
    private int[] rank;

    public UnionFind(int capacity) {
        par = new int[capacity];
        rank = new int[capacity];
    }

    public void init(int n) {
        for (int i = 0; i < n; i++) {
            par[i] = i;
            rank[i] = 0;
        }
    }

    public int getRoot(int x) {
        if (par[x] == x) {
            return x;
        } else {
            par[x] = getRoot(par[x]);
            return par[x];
        }
    }

    public void unite(int x, int y) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y) {
            return;
        }
        if (rank[x] < rank[y]) {
            par[x] = y;
        } else {
            par[y] = x;
            if (rank[x] == rank[y]) {
                rank[x]++;
            }
        }
    }

    public boolean isSame(int x, int y) {
        return getRoot(x) == getRoot(y);
    }
}

class Pair<T extends Comparable<T>, S> implements Comparable<Pair<T, S>> {
    public T first;
    public S second;

    public Pair(T t, S s) {
        this.first = t;
        this.second = s;
    }

    private int hash = 0;

    @Override
    public int hashCode() {
        if (hash == 0) {
            final int prime = 31;
            int result = 1;
            result = prime * result + ((first == null) ? 0 : first.hashCode());
            result = prime * result + ((second == null) ? 0 : second.hashCode());
            hash = result;
        }
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Pair<T, S> other = (Pair<T, S>) obj;
        if (first == null) {
            if (other.first != null)
                return false;
        } else if (!first.equals(other.first))
            return false;
        if (second == null) {
            if (other.second != null)
                return false;
        } else if (!second.equals(other.second))
            return false;
        return true;
    }

    @Override
    public int compareTo(Pair<T, S> o) {
        return first.compareTo(o.first);
    }
}

class IntQueue {
    private int[] queue;
    private int current;
    private int size;

    public IntQueue(int capacity) {
        queue = new int[capacity];
    }

    public void clear() {
        init();
    }

    public void init() {
        current = 0;
        size = 0;
    }

    public boolean isEmpty() {
        return current == size;
    }

    public int poll() {
        return queue[current++];
    }

    public void add(int value) {
        queue[size++] = value;
    }
}

class IntSet {
    private static final int EMPTY = -1;
    private int size;
    private int[] indexToValue;
    private int[] valueToIndex;

    public IntSet(int capacity) {
        this.size = 0;
        indexToValue = new int[capacity];
        valueToIndex = new int[capacity];
        Arrays.fill(valueToIndex, EMPTY);
    }

    public boolean add(int value) {
        if (valueToIndex[value] != EMPTY) {
            return false;
        }
        indexToValue[size] = value;
        valueToIndex[indexToValue[size]] = size;
        size++;
        return true;
    }

    public boolean remove(int index) {
        if (size == 0) {
            return false;
        }
        assert index < size;
        int swap = indexToValue[index];
        indexToValue[index] = indexToValue[size - 1];
        indexToValue[size - 1] = swap;

        valueToIndex[indexToValue[index]] = index;
        valueToIndex[indexToValue[size - 1]] = EMPTY;

        size--;
        return true;
    }

    public boolean removeValue(int value) {
        int index = indexOf(value);
        if (index == EMPTY) {
            return false;
        }
        remove(index);
        return true;
    }

    public int get(int index) {
        assert index < size;
        return indexToValue[index];
    }

    public int indexOf(int value) {
        return valueToIndex[value];
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size() <= 0;
    }

    public void clear() {
        for (; size() > 0;) {
            remove(0);
        }
    }

    public boolean contains(int value) {
        return indexOf(value) != EMPTY;
    }

}

class TextFileIO {
    public static String read0(File file, String encoding) {
        StringBuilder sb = new StringBuilder();
        BufferedReader reader = null;
        try {
            reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding));
            char[] ch = new char[50000];
            int read;
            while ((read = reader.read(ch)) > 0) {
                String s = new String(ch, 0, read);
                sb.append(s);
            }
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (reader != null) {
                try {
                    reader.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
        return sb.toString();
    }

    public static String read(File file) {
        return read(file, "UTF-8");
    }

    public static String read(File file, String encoding) {
        StringBuilder sb = new StringBuilder();
        BufferedReader reader = null;
        try {
            reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding));
            for (String line; (line = reader.readLine()) != null;) {
                sb.append(line + "\n");
            }
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (reader != null) {
                try {
                    reader.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
        return sb.toString();
    }

    public static String[] read2(File file, String encoding) {
        ArrayList<String> list = new ArrayList<String>();
        BufferedReader reader = null;
        try {
            reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding));
            for (String line; (line = reader.readLine()) != null;) {
                list.add(line);
            }
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (reader != null) {
                try {
                    reader.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
        return (String[]) list.toArray(new String[list.size()]);
    }

    public static ArrayList<String> readLines(File file) {
        return read3(file, "UTF-8");
    }

    public static ArrayList<String> readLines(File file, String encoding) {
        return read3(file, encoding);
    }

    public static ArrayList<String> read3(File file) {
        return read3(file, "UTF-8");
    }

    public static ArrayList<String> read3(File file, String encoding) {
        ArrayList<String> res = new ArrayList<String>();

        try (BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding))) {
            for (String line; (line = reader.readLine()) != null;) {
                res.add(line);
            }
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return res;
    }

    public static List<String> readLines(Path file, Charset encoding) {
        try (BufferedReader reader = Files.newBufferedReader(file, encoding)) {
            return reader.lines().collect(Collectors.toList());
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
        ArrayList<String> res = new ArrayList<String>();
        return res;
    }

    public static ArrayList<String> readFirstNLines(int numLines, File file) {
        return readFirstNLines(numLines, file, "UTF-8");
    }

    public static ArrayList<String> readFirstNLines(int numLines, File file, String encoding) {
        ArrayList<String> res = new ArrayList<String>();
        BufferedReader reader = null;
        try {
            reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding));
            for (String line; (line = reader.readLine()) != null;) {
                res.add(line);
                if (res.size() >= numLines) {
                    break;
                }
            }
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (reader != null) {
                try {
                    reader.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
        return res;
    }

    private static void mkParents(File file) {
        File parentFile = file.getParentFile();
        if (!parentFile.exists()) {
            for (int i = 0; i < 5; i++) {
                if (parentFile.mkdirs()) {
                    break;
                }
            }
        }
    }

    public static void write(String contents, File file, String encoding) {
        mkParents(file);

        BufferedWriter writer = null;
        try {
            writer = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(file), encoding));
            writer.write(contents);
            writer.flush();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (writer != null) {
                try {
                    writer.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
    }

    public static void write(String contents, Path file, Charset encoding) {
        try {
            Files.createDirectories(file.getParent());
        } catch (IOException e) {
            e.printStackTrace();
        }
        try (BufferedWriter writer = Files.newBufferedWriter(file, encoding)) {
            writer.write(contents);
            writer.flush();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static void write(String contents, Path file) {
        write(contents, file, StandardCharsets.UTF_8);
    }

    public static void append(String contents, File file, String encoding) {
        mkParents(file);

        BufferedWriter writer = null;
        try {
            writer = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(file, true), encoding));
            writer.append(contents);
            writer.flush();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (writer != null) {
                try {
                    writer.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
    }

    public static void appendln(String contents, File file, String encoding) {
        append(contents + "\n", file, encoding);
    }

    public static void write(String contents) {
        write(contents, new File("./debug.txt"), "UTF-8");
    }

    public static void write(String contents, File file) {
        write(contents, file, "UTF-8");
    }

    public static void writeln(String contents) {
        write(contents + "\n", new File("./debug.txt"), "UTF-8");
    }

    public static void writeln(String contents, File file) {
        write(contents + "\n", file, "UTF-8");
    }

    public static void append(String contents) {
        append(contents, new File("./debug.txt"), "UTF-8");
    }

    public static void append(String contents, File file) {
        append(contents, file, "UTF-8");
    }

    public static void appendln(String contents) {
        append(contents + "\n", new File("./debug.txt"), "UTF-8");
    }

    public static void appendln(String contents, File file) {
        append(contents + "\n", file, "UTF-8");
    }

    public static String read() {
        return read(new File("./debug.txt"), "UTF-8");
    }

    public static int calculateNumLines(File file) {
        return calculateNumLines(file, "UTF-8");
    }

    public static int calculateNumLines(File file, String encoding) {
        int numLines = 0;
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding))) {
            for (String line; (line = reader.readLine()) != null;) {
                numLines++;
            }
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return numLines;
    }

    public static void printRandomLines(double d, File file) {
        printRandomLines(d, file, "UTF-8");
    }

    public static void printRandomLines(double d, File file, String encoding) {
        Random rng = new Random(System.nanoTime());
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding))) {
            for (String line; (line = reader.readLine()) != null;) {
                if (rng.nextDouble() < d) {
                    Utils.debug(line);
                }
            }
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

}

class MeanHelper {
    private double max;
    private double min;
    private double sum;
    private double sumSquared;
    private double sumCubed;
    private double sumFourth;
    private int count;

    public MeanHelper() {
        clear();
    }

    public void add(double value) {
        max = Math.max(max, value);
        min = Math.min(min, value);
        sum += value;
        double valueSquared = value * value;
        sumSquared += valueSquared;
        sumCubed += valueSquared * value;
        sumFourth += valueSquared * valueSquared;
        count++;
    }

    public void add(double value, double number) {
        max = Math.max(max, value);
        min = Math.min(min, value);
        sum += value * number;
        double valueSquared = value * value;
        sumSquared += valueSquared * number;
        sumCubed += valueSquared * value * number;
        sumFourth += valueSquared * valueSquared * number;
        count += number;
    }

    public double kurtosis(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        double sigma = standardDeviation(0);
        if (sigma == 0) {
            return 0;
        }
        double mu = mean(0);
        return (sumFourth - 4.0 * mu * sumCubed + 6.0 * mu * mu * sumSquared - 3.0 * mu * mu * mu * sum) / count / (sigma * sigma * sigma * sigma);
    }

    public double skewness(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        double sigma = standardDeviation(0);
        if (sigma == 0) {
            return 0;
        }
        double mu = mean(0);
        return (sumCubed - 3.0 * mu * sumSquared + 2.0 * mu * mu * sum) / count / (sigma * sigma * sigma);
    }

    public double mean() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        return sum / count;
    }

    public double mean(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        return sum / count;
    }

    public double sumOfSquaredError() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        return sumSquared - sum * sum / count;
    }

    public double sumOfSquaredError(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        return sumSquared - sum * sum / count;
    }

    public double variance() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        double E_XX = sumSquared / count;
        double E_X = sum / count;
        return E_XX - E_X * E_X;
    }

    public double variance(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        double E_XX = sumSquared / count;
        double E_X = sum / count;
        return E_XX - E_X * E_X;
    }

    public double unbiasedVariance() {
        if (count - 1 == 0) {
            throw new AssertionError();
        }
        return (count * variance()) / (count - 1);
    }

    private double unbiasedVariance(double defaultValue) {
        if (count - 1 == 0) {
            return defaultValue;
        }
        return (count * variance()) / (count - 1);
    }

    public double standardDeviation() {
        return Math.sqrt(variance());
    }

    public double standardDeviation(double defaultValue) {
        return Math.sqrt(variance(defaultValue));
    }

    public double unbiasedStandardDeviation() {
        return Math.sqrt(unbiasedVariance());
    }

    public double unbiasedStandardDeviation(double defaultValue) {
        return Math.sqrt(unbiasedVariance(defaultValue));
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public void clear() {
        max = Double.NEGATIVE_INFINITY;
        min = Double.POSITIVE_INFINITY;
        sum = 0;
        sumSquared = 0;
        sumCubed = 0;
        sumFourth = 0;
        count = 0;
    }

    public double max() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        return max;
    }

    public double max(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        return max;
    }

    public double min() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        return min;
    }

    public double min(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        return min;
    }

    public int count() {
        return count;
    }

    public double sum() {
        return sum;
    }

    public double sumSquared() {
        return sumSquared;
    }
}

class Graph implements IGraph {
    private ArrayList<IntSet2> graph;
    private int numNodes;

    public Graph(int numNodes) {
        this.numNodes = numNodes;

        graph = new ArrayList<>();
        for (int i = 0; i < numNodes; i++) {
            graph.add(new IntSet2());
        }
    }

    @Override
    public int numNodes() {
        return numNodes;
    }

    @Override
    public void addEdge(int node, int node2) {
        graph.get(node).add(node2);
        graph.get(node2).add(node);
    }

    @Override
    public void removeEdge(int node, int node2) {
        graph.get(node).removeValue(node2);
        graph.get(node2).removeValue(node);
    }

    @Override
    public void clearEdges() {
        for (int node = 0; node < numNodes; node++) {
            graph.get(node).clear();
        }
    }

    @Override
    public void copy(IGraph g) {
        clearEdges();
        for (int node = 0; node < g.numNodes(); node++) {
            for (int i = 0; i < g.degree(node); i++) {
                int vertex = g.getNode(node, i);
                graph.get(node).add(vertex);
            }
        }
    }

    @Override
    public int getNode(int node, int index) {
        return graph.get(node).get(index);
    }

    @Override
    public int degree(int node) {
        return graph.get(node).size();
    }

    @Override
    public boolean hasEdge(int node, int node2) {
        return graph.get(node).contains(node2);
    }

}

interface IGraph {

    void addEdge(int node, int node2);

    void removeEdge(int node, int node2);

    boolean hasEdge(int node, int node2);

    void clearEdges();

    int getNode(int node, int index);

    int degree(int node);

    int numNodes();

    void copy(IGraph g);

}

final class Function {
    private Function() {
    }

    public static final double[] lower_bound_of_diam_aspl(int nnodes, int degree) {
        int diam = -1;
        double aspl = 0.0;
        int n = 1;
        int r = 1;
        while (true) {
            int tmp = n + degree * (int) Math.pow(degree - 1, r - 1);
            if (tmp >= nnodes) {
                break;
            }
            n = tmp;
            aspl += r * degree * Math.pow(degree - 1, r - 1);
            diam = r;
            r += 1;
        }
        diam += 1;
        aspl += diam * (nnodes - n);
        aspl /= (nnodes - 1);
        return new double[] { diam, aspl };
    }
}

class GifWriter {
    ImageWriter iw = ImageIO.getImageWritersByFormatName("gif").next();
    BufferedImage buffer;
    boolean finish = false;

    GifWriter(String filename) {
        File outfile = new File(filename);
        if (outfile.exists()) {
            Utils.debug("outfile.delete()", outfile.delete());
        }
        try {
            ImageOutputStream ios = ImageIO.createImageOutputStream(outfile);
            iw.setOutput(ios);
            iw.prepareWriteSequence(null);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    void add(BufferedImage buffer) {
        if (finish)
            return;
        try {
            iw.writeToSequence(new IIOImage(buffer, null, null), null);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    void close() {
        if (finish)
            return;
        try {
            finish = true;
            iw.endWriteSequence();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

class IntSet2 {
    private static final int EMPTY = -1;
    private ArrayList<Integer> indexToValue;
    private HashMap<Integer, Integer> valueToIndex;

    public IntSet2() {
        indexToValue = new ArrayList<>();
        valueToIndex = new HashMap<>();
    }

    public boolean add(Integer value) {
        if (valueToIndex.get(value) != null) {
            return false;
        }
        Integer size = Integer.valueOf(indexToValue.size());
        indexToValue.add(value);
        if (valueToIndex.containsKey(value)) {
            valueToIndex.replace(value, size);
        } else {
            valueToIndex.put(value, size);
        }
        return true;
    }

    public boolean remove(int index) {
        if (size() == 0) {
            return false;
        }
        assert index < size();
        swap(index, size() - 1);
        Integer remove = indexToValue.remove(size() - 1);
        valueToIndex.remove(remove);
        return true;
    }

    public boolean removeValue(Integer value) {
        int index = indexOf(value);
        if (index == EMPTY) {
            return false;
        }
        remove(index);
        return true;
    }

    public int get(int index) {
        assert index < size();
        return indexToValue.get(index).intValue();
    }

    public int indexOf(Integer value) {
        Integer e = valueToIndex.get(value);
        return e == null ? EMPTY : e.intValue();
    }

    public int size() {
        return indexToValue.size();
    }

    public boolean isEmpty() {
        return size() <= 0;
    }

    public void clear() {
        for (; size() > 0;) {
            remove(0);
        }
    }

    public boolean contains(Integer value) {
        return indexOf(value) != EMPTY;
    }

    public void swap(int index, int index2) {
        assert index < size();
        assert index2 < size();

        {
            Integer swap = indexToValue.get(index);
            indexToValue.set(index, indexToValue.get(index2));
            indexToValue.set(index2, swap);
        }
        if (valueToIndex.containsKey(indexToValue.get(index))) {
            valueToIndex.replace(indexToValue.get(index), index);
        } else {
            valueToIndex.put(indexToValue.get(index), index);
        }
        if (valueToIndex.containsKey(indexToValue.get(index2))) {
            valueToIndex.replace(indexToValue.get(index2), index2);
        } else {
            valueToIndex.put(indexToValue.get(index2), index2);
        }

    }

}

class TimerManager {
    HashMap<String, Timer> map = new HashMap<>();

    public void start(String id) {
        if (map.get(id) == null) {
            map.put(id, new Timer());
        }
        Timer timer = map.get(id);
        timer.setDescription(id);
        timer.start();
    }

    public void stop(String id) {
        if (map.get(id) == null) {
            map.put(id, new Timer());
        }
        Timer timer = map.get(id);
        timer.setDescription(id);
        timer.stop();
    }

    public void print() {
        ArrayList<Timer> timers = new ArrayList<>();
        timers.addAll(map.values());
        Collections.sort(timers);
        for (int i = 0; i < timers.size(); i++) {
            timers.get(i).print();
        }
    }
}

class Timer implements Comparable<Timer> {
    private double time;
    private long start;
    private long stop;
    private int count;
    private String description;
    private boolean isRunning;

    public Timer() {
        reset();
    }

    @Override
    public int compareTo(Timer o) {
        if (time < o.time) {
            return 1;
        }
        if (time > o.time) {
            return -1;
        }
        return 0;
    }

    public int getCount() {
        return count;
    }

    public String getDescription() {
        return description;
    }

    public long getStart() {
        return start;
    }

    public long getStop() {
        return stop;
    }

    public double getTime() {
        return time;
    }

    public boolean isRunning() {
        return isRunning;
    }

    public void print() {
        if (count > 0) {
            Utils.debug(String.format("time, %10s, count, %10d, time/count, %12.9f, %s", TimeManager.toString(time), count, time / count, description));
        }
    }

    public void reset() {
        time = 0;
        start = 0;
        stop = 0;
        count = 0;
        isRunning = false;
    }

    public void setDescription(String description) {
        assert this.description == null || this.description.equals(description);
        if (this.description == null) {
            this.description = description;
        }
    }

    public void start() {
        assert isRunning == false;
        isRunning = true;
        start = System.nanoTime();
    }

    public void stop() {
        assert isRunning == true;
        stop = System.nanoTime();
        count++;
        time += (stop - start) * 1e-9;
        isRunning = false;
    }
}

class TimeManager {
    private long start;
    private int count;

    public TimeManager() {
        init();
    }

    public int getCount() {
        return count;
    }

    public double getSecond() {
        count++;
        return (System.nanoTime() - start) * 1e-9;
    }

    public long getTime() {
        count++;
        return System.nanoTime() - start;
    }

    public void init() {
        init(System.nanoTime());
    }

    public void init(long start) {
        this.start = start;
        count = 0;
    }

    public String toString() {
        return toString(getSecond());
    }

    public String getSecondString() {
        return toString(getSecond());
    }

    public static final String toString(double second) {
        if (second < 60) {
            return String.format("%5.2fs", second);
        } else if (second < 60 * 60) {
            int minute = (int) (second / 60);
            return String.format("%2dm%2ds", minute, (int) (second % 60));
        } else {
            int hour = (int) (second / (60 * 60));
            int minute = (int) (second / 60);
            return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));
        }
    }

}