problem https://github.com/kosakkun/Typical-MM/tree/master/RectilinearSteinerTree

Approach  山登り法を2種類使いました。

  • 最初の山登り法で、点を追加、削除、移動させる近傍で、シュタイナー木(最小全域木)の上限を抑えます。
  • 2回めの山登り法で、あるパスを削除して、別のパスを追加し直す近傍で、うまく経路を重複させます。
    • この後行われた、MM109のように、ある点を通るパスを全部削除して追加し直すともっと良くなると思います。
      • MM107の頃にやってました。
  • 高速化はしてないです。



seed目安my
1629538
2854780
3664603
4480430
5563498
6688601
7934830
8850759
9581517
10624556


source code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

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

    final int[] dc = { 1, 0, -1, 0 };
    final int[] dr = { 0, 1, 0, -1 };
    final int size = 100;

    private int[] c;
    private int[] r;

    private int N;
    private int M;
    private boolean[][] used;
    private boolean[][] used2;

    public static void main(String[] args) {
        new RectilinearSteinerTree().run();
    }

    private void run() {
        read();
        solve();
        write();
    }

    ArrayList solution = new ArrayList<>();
    private long score;

    private void solve() {
        sa.endTime = 9.5 * 0.666;
        SAForMST();
        sa.endTime = 9.5;
        SAForScore();

        for (ArrayList path : pathList) {
            for (Node node : path) {
                int r = node.r;
                int c = node.c;

                if (used[r][c]) {
                    continue;
                }
                used[r][c] = true;
                solution.add(new State(c, r, 0));

            }
        }
//        ArrayList> listlist = new ArrayList<>();
//        for (int i = 0; i < N; i++) {
//            addPoint(0, i);
//        }

    }

    private ArrayList> pathList = new ArrayList<>();
    private ArrayList fromAndToList = new ArrayList<>();
    private MinimumSpanningTree mst;

    private void SAForScore() {
        Utils.debug("M", M);
        for (int i = N; i < N + M; i++) {
            used[r[i]][c[i]] = true;
            solution.add(new State(c[i], r[i], 0));
        }

        mst = new MinimumSpanningTree(N + M);
        for (int from = 0; from < N + M; from++) {
            for (int to = 0; to < N + M; to++) {
                mst.addEdge(from, to, manhattanDistance(from, to));
            }
        }
        mst.kruskal();

        UnionFind unionFind = new UnionFind();
        unionFind.init(N + M);

        score = M;
//        boolean[] used = new boolean[N];
        for (int from = 0; from < N + M; from++) {
//            used[from] = true;
            ArrayList edges = mst.G.get(from);
            for (Edge edge : edges) {
                int to = edge.to;
//                if (used[to]) {
//                    continue;
//                }
//                used[to] = true;

                if (unionFind.isSame(from, to)) {
                    continue;
                }
                unionFind.unite(from, to);

                ArrayList path = dijkstra(from, to);

                pathList.add(path);
                fromAndToList.add((from << 16) | to);

                for (Node node : path) {
                    int r = node.r;
                    int c = node.c;
                    if (used[r][c]) {
                        continue;
                    }
                    count[r][c]++;
                }

                score += path.get(path.size() - 1).numCells;

//                addPoint(from, to);
            }

        }

        double second = Math.ceil(watch.getSecond());

        sa.init();
        Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), "score", (long) score, String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
        for (;; ++sa.numIterations) {
            if ((sa.numIterations & ((1 << 7) - 1)) == 0) {
                sa.update();

                if (sa.isTLE()) {
                    Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), "score", (long) score, String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
                    break;
                }

                if (sa.time > second) {
                    second++;
                    Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), "score", (long) score, String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
                }
            }

            mutate();
        }

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

    }

    private void SAForMST() {
        double second = Math.ceil(watch.getSecond());

        score = calculateMST();

        sa.init();
        Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), "score", (long) score, String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
        for (;; ++sa.numIterations) {
            if ((sa.numIterations & ((1 << 3) - 1)) == 0) {
                sa.update();

                if (sa.isTLE()) {
                    Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), "score", (long) score, String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
                    break;
                }

                if (sa.time > second) {
                    second++;
                    Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), "score", (long) score, String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
                }
            }

            mutateForMST();
        }

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

    private void mutateForMST() {
        double random = 3 * rng.nextDouble();
        if (random < 1) {
            addPoint(0);
        } else if (random < 2) {
            removePoint(1);
        } else if (random < 3) {
            movePoint(2);
        }

    }

    private void addPoint(int i) {
        int newR = (int) (size * rng.nextDouble());
        int newC = (int) (size * rng.nextDouble());
        while (used[newR][newC] || used2[newR][newC]) {
            newR = (int) (size * rng.nextDouble());
            newC = (int) (size * rng.nextDouble());
        }

        r[N + M] = newR;
        c[N + M] = newC;
        M++;

        double deltaScore = calculateMST() - score;
        if (sa.accept(deltaScore / Math.abs(score))) {
            score += deltaScore;
            used2[newR][newC] = true;
        } else {
            M--;
        }
    }

    private void removePoint(int i) {
        if (M == 0) {
            return;
        }

        int m = (int) (M * rng.nextDouble());

        {
            int swap = r[N + m];
            r[N + m] = r[N + M - 1];
            r[N + M - 1] = swap;
        }
        {
            int swap = c[N + m];
            c[N + m] = c[N + M - 1];
            c[N + M - 1] = swap;
        }

        used2[r[N + M - 1]][c[N + M - 1]] = !true;
        M--;

        double deltaScore = calculateMST() - score;
        if (sa.accept(deltaScore / Math.abs(score))) {
            score += deltaScore;
        } else {
            M++;
            used2[r[N + M - 1]][c[N + M - 1]] = true;
        }
    }

    private void movePoint(int i) {
        if (M == 0) {
            return;
        }

        int m = (int) (M * rng.nextDouble());

        int currentR = r[N + m];
        int currentC = c[N + m];

        int newR = r[N + m] - 1 + (int) (3 * rng.nextDouble());
        int newC = c[N + m] - 1 + (int) (3 * rng.nextDouble());
        newR = Math.min(size - 1, Math.max(0, newR));
        newC = Math.min(size - 1, Math.max(0, newC));
        if (used[newR][newC] || used2[newR][newC]) {
//            newR = newR - 1 + (int) (3 * rng.nextDouble());
//            newC = newC - 1 + (int) (3 * rng.nextDouble());
//            newR = Math.min(size - 1, Math.max(0, newR));
//            newC = Math.min(size - 1, Math.max(0, newC));
            return;
        }

        r[N + m] = newR;
        c[N + m] = newC;

        double deltaScore = calculateMST() - score;
        if (sa.accept(deltaScore / Math.abs(score))) {
            score += deltaScore;
            used2[currentR][currentC] = !true;
            used2[newR][newC] = true;
        } else {
            r[N + m] = currentR;
            c[N + m] = currentC;
        }
    }

    private long calculateMST() {
        MinimumSpanningTree mst = new MinimumSpanningTree(N + M);
        for (int from = 0; from < N + M; from++) {
            for (int to = 0; to < N + M; to++) {
                mst.addEdge(from, to, manhattanDistance(from, to));
            }
        }
        return mst.kruskal();
    }

    private long calculateScore() {
        MinimumSpanningTree mst = new MinimumSpanningTree(N + M);
        for (int from = 0; from < N + M; from++) {
            for (int to = 0; to < N + M; to++) {
                mst.addEdge(from, to, manhattanDistance(from, to));
            }
        }
        return mst.kruskal();
    }

    private void addPoint2(int from, int to) {

        for (int c = this.c[from], r = this.r[from];;) {
            if (c == this.c[to] && r == this.r[to]) {
                break;
            }

            if (!used[r][c]) {
                used[r][c] = true;
                solution.add(new State(c, r, 0));
            }

            if (c != this.c[to]) {
                if (c < this.c[to]) {
                    c++;
                } else {
                    c--;
                }
            } else if (r != this.r[to]) {
                if (r < this.r[to]) {
                    r++;
                } else {
                    r--;
                }
            }
        }

    }

    int[][] count = new int[size][size];

    private void addPoint(int from, int to) {
        ArrayList path = dijkstra(from, to);
        addPath(path);
    }

    private ArrayList dijkstra(int from, int to) {
        Node toNode = null;
        {
            PriorityQueue queue = new PriorityQueue<>();
            int[][] used = new int[size][size];
            for (int r = 0; r < size; r++) {
                Arrays.fill(used[r], (int) 1e9);
            }

            {
                queue.add(new Node(null, r[from], c[from], 0));
                used[r[from]][c[from]] = 0;
//            count[r[from]][c[from]]++;
            }
            for (; !queue.isEmpty();) {
                Node node = queue.poll();
                int numCells = node.numCells;
                int r = node.r;
                int c = node.c;

                if (r == this.r[to] && c == this.c[to]) {
                    toNode = node;
                    break;
                }

                for (int d = 0; d < dr.length; d++) {
                    int nr = r + dr[d];
                    int nc = c + dc[d];
                    if (nr < 0 || nr >= size) {
                        continue;
                    }
                    if (nc < 0 || nc >= size) {
                        continue;
                    }

                    int nNumCells = numCells;
                    if (!this.used[nr][nc] && count[nr][nc] == 0) {
                        nNumCells++;
                    }

                    if (nNumCells >= used[nr][nc]) {
                        continue;
                    }
                    used[nr][nc] = nNumCells;
                    queue.add(new Node(node, nr, nc, nNumCells));
//                count[nr][nc]++;
                }

            }
        }

        if (toNode == null) {
            return null;
        }

        ArrayList path = reverse(toList(toNode));
        return path;
    }

    private void addPath(ArrayList list) {
        for (int i = 0; i < list.size(); i++) {
            Node n = list.get(i);
            int r = n.r;
            int c = n.c;
            count[r][c]++;
            if (used[r][c]) {
                continue;
            }
            if (used2[r][c]) {
                continue;
            }
            used2[r][c] = true;
            solution.add(new State(c, r, 0));
        }
    }

    private void removePath(ArrayList list) {
        for (int i = 0; i < list.size(); i++) {
            Node n = list.get(i);
            int r = n.r;
            int c = n.c;
//            if (!used2[r][c]) {
//                continue;
//            }
            used2[r][c] = !true;
            count[r][c]--;
            solution.remove(new State(c, r, 0));
        }
    }

    public static final ArrayList toList(Node node) {
        ArrayList list = new ArrayList<>();
        for (Node current = node; current != null; current = current.parent) {
            list.add(current);
        }
        return list;
    }

    public static final  ArrayList reverse(ArrayList list) {
        for (int l = 0, r = list.size() - 1; l < r; l++, r--) {
            list.set(r, list.set(l, list.get(r)));
        }
        return list;
    }

    private int manhattanDistance(int i, int j) {
        return Math.abs(c[i] - c[j]) + Math.abs(r[i] - r[j]);
    }

    private Point FermatPoint(int a, int b, int c) {
        double da = dist(b, c);
        double db = dist(a, c);
        double dc = dist(a, b);

        if (da * da >= db * db + dc * dc + db * dc)
            return null;
        if (db * db >= dc * dc + da * da + dc * da)
            return null;
        if (dc * dc >= da * da + db * db + da * db)
            return null;

        double A = Math.acos((db * db + dc * dc - da * da) / (2 * db * dc));
        double B = Math.acos((dc * dc + da * da - db * db) / (2 * dc * da));
        double C = Math.acos((da * da + db * db - dc * dc) / (2 * da * db));

        double ra = csc(A + Math.PI / 3);
        double rb = csc(B + Math.PI / 3);
        double rc = csc(C + Math.PI / 3);

        double wa = da * ra;
        double wb = db * rb;
        double wc = dc * rc;

        double wall = wa + wb + wc;

        double x = this.c[a] * wa + this.c[b] * wb + this.c[c] * wc;
        double y = this.r[a] * wa + this.r[b] * wb + this.r[c] * wc;
        return new Point((int) (0.5 + x / wall), (int) (0.5 + y / wall));
    }

    private double csc(double x) {
        return 1.0 / Math.sin(x);
    }

    private double dist(int a, int b) {
        int dx = c[a] - c[b];
        int dy = r[a] - r[b];
        return Math.sqrt(dx * dx + dy * dy);
    }

//    private void SA() {
//        double second = Math.ceil(watch.getSecond());
//
//        sa.init();
//        for (;; ++sa.numIterations) {
//            if ((sa.numIterations & ((1 << 7) - 1)) == 0) {
//                sa.update();
//
//                if (sa.isTLE()) {
//                    Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), "score", (long) score, "diff", (long) sumDiff, "pow", String.format("%.3f", e * e), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
//                    break;
//                }
//
//                if (sa.time > second) {
//                    second++;
//                    Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), "score", (long) score, "diff", (long) sumDiff, "pow", String.format("%.3f", e * e), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
//                }
//            }
//
//            mutate();
//        }
//
//        Utils.debug("SA", "time", watch.getSecondString());
//
//    }

    private void mutate() {
        double random = 1 * rng.nextDouble();
        if (random < 1) {
            removeAndAdd(0);
        }
    }

    private void removeAndAdd(int index0) {
        int index = (int) (pathList.size() * rng.nextDouble());

//        Collections.swap(pathList, index, pathList.size() - 1);
//        Collections.swap(fromAndToList, index, fromAndToList.size() - 1);
//        index = pathList.size() - 1;

        ArrayList path = pathList.get(index);
//        int before = path.get(path.size() - 1).numCells;

        int before = 0;
        for (Node node : path) {
            int r = node.r;
            int c = node.c;
            if (used[r][c]) {
                continue;
            }
            count[r][c]--;
            if (count[r][c] == 0) {
                before++;
            }
        }

        int v = fromAndToList.get(index).intValue();
        int from = v >>> 16;
        int to = v & ((1 << 16) - 1);

        ArrayList newPath = rng.nextDouble() < 0.5 ? dijkstra(from, to) : dijkstra(to, from);

        int after = newPath.get(newPath.size() - 1).numCells;
//        int after  = 0;
//        for (Node node : path) {
//            int r = node.r;
//            int c = node.c;
//            if (used[r][c]) {
//                continue;
//            }
//            count[r][c]--;
//            if (count[r][c] == 0) {
//                before++;
//            }
//        }

        double deltaScore = after - before;

        if (sa.accept(deltaScore / Math.abs(score))) {
//            if (after != before) {
//                Utils.debug("after, before, path.size(), newPath.size()", after, before, path.size(), newPath.size());
//            }
            score += deltaScore;
            pathList.set(index, newPath);
            for (Node node : newPath) {
                int r = node.r;
                int c = node.c;
                if (used[r][c]) {
                    continue;
                }
                count[r][c]++;
            }
//            int score2 = M;
//            for (ArrayList path2 : pathList) {
//                score2 += path2.get(path2.size() - 1).numCells;
//            }
//            if (score2 != score) {
//                Utils.debug(score2, score);
//            }
        } else {
            for (Node node : path) {
                int r = node.r;
                int c = node.c;
                if (used[r][c]) {
                    continue;
                }
                count[r][c]++;
            }
//            int score2 = M;
//            for (ArrayList path2 : pathList) {
//                score2 += path2.get(path2.size() - 1).numCells;
//            }
//            if (score2 != score) {
//                Utils.debug(score2, score);
//            }
        }
    }

    private boolean isConnected(UnionFind unionFind) {
        for (int i = 0; i < N; i++) {
            if (unionFind.getRoot(r[0] * size + c[0]) != unionFind.getRoot(r[i] * size + c[i])) {
                return false;
            }
        }
        return true;
    }

    private void print(double[][] life) {
        for (int r = 0; r < size; r++) {
            for (int c = 0; c < size; c++) {
                System.err.format("%6.3f", life[r][c]);
            }
            System.err.println();
        }
    }

    private void print(boolean[][] b) {
        for (int r = 0; r < size; r++) {
            for (int c = 0; c < size; c++) {
                System.err.format("%s", used[c][r] ? "X" : b[c][r] ? "*" : " ");
            }
            System.err.println();
        }
        System.err.println();
    }

    private void read() {
        try (Scanner sc = new Scanner(System.in)) {
            N = sc.nextInt();
            Utils.debug("N", N);
            used = new boolean[size][size];
            used2 = new boolean[size][size];
            c = new int[10 * N];
            r = new int[10 * N];
            for (int i = 0; i < N; i++) {
                c[i] = sc.nextInt();
                r[i] = sc.nextInt();
                used[r[i]][c[i]] = true;
            }

        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private void write() {
//        System.out.println(size * size - N);
//        for (int x = 0; x < size; x++) {
//            for (int y = 0; y < size; y++) {
//                if (!used[x][y]) {
//                    System.out.println(x + " " + y);
//                }
//            }
//        }
//        System.out.flush();
        System.out.println(solution.size());
        for (State state : solution) {
            System.out.println(state.x + " " + state.y);
        }
        System.out.flush();
    }

}

class State implements Comparable {
    int x;
    int y;
    double life;

    public State(int x, int y, double life) {
        super();
        this.x = x;
        this.y = y;
        this.life = life;
    }

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

class SAState {

    public static final boolean useTime = true;

    public double startTime = 0;
    public double endTime = 9.5;
    public double time = startTime;

    public double startTemperature = 0;
    public double endTemperature = 0;
    public double inverseTemperature = 1.0 / startTemperature;
    public double lastAcceptTemperature = startTemperature;

    public double startRange = 15;
    public double endRange = 0;
    public double range = startRange;

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

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

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

        update();
        lastAcceptTemperature = inverseTemperature;
    }

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

    public void updateTemperature() {
        inverseTemperature = 1.0 / (endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), 1.0));
    }

    public void updateRange() {
        range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
    }

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

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

    public boolean accept(double deltaScore) {
        return acceptS(deltaScore);
    }

    public boolean acceptB(double deltaScore) {
        validIterations++;

        if (deltaScore > -1e-9) {
            acceptIterations++;
            return true;
        }

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

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

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

    public boolean acceptS(double deltaScore) {
        validIterations++;

        if (deltaScore < 1e-9) {
            acceptIterations++;
            return true;
        }

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

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

        if (RectilinearSteinerTree.rng.nextDouble() < Math.exp(-deltaScore * inverseTemperature)) {
            acceptIterations++;
            lastAcceptTemperature = inverseTemperature;
            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 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 void init(int n) {
        par = new int[n];
        rank = new 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 Edge {
    int to;
    int cost;

    public Edge(int to, int cost) {
        this.to = to;
        this.cost = cost;
    }
}

class Edge2 {
    int from;
    int to;
    int cost;

    public Edge2(int from, int to, int cost) {
        this.from = from;
        this.to = to;
        this.cost = cost;
    }
}

class MinimumSpanningTree {

    private static final int INF = (int) 1e9;
    ArrayList> G;
    private ArrayList edges;
    private int numVertexes;
    // private int[] dist;
    // private int[] prevv;
    // private int[] preve;

    public MinimumSpanningTree(int v) {
        clear(v);
    }

    public void clear(int v) {
        this.numVertexes = v;

        G = new ArrayList>();
        for (int i = 0; i < v; i++) {
            G.add(new ArrayList());
        }
        edges = new ArrayList();

        // dist = new int[v];
        // prevv = new int[v];
        // preve = new int[v];
    }

    public void addEdge(int from, int to, int cost) {
        assert cost >= 0;
        assert cost <= INF;

        // G.get(from).add(new Edge(to, cost));
        // G.get(to).add(new Edge(from, cost));

        edges.add(new Edge2(from, to, cost));
    }

    public int kruskal() {
        UnionFind unionFind = new UnionFind();
        unionFind.init(numVertexes);

        Collections.sort(edges, new Comparator() {
            @Override
            public int compare(Edge2 o1, Edge2 o2) {
                if (o1.cost < o2.cost) {
                    return -1;
                }
                if (o1.cost > o2.cost) {
                    return 1;
                }
                return 0;
            }
        });

        int cost = 0;
        int numEdges = 0;
        for (Edge2 edge2 : edges) {
            if (unionFind.isSame(edge2.from, edge2.to)) {
                continue;
            }
            unionFind.unite(edge2.from, edge2.to);

            G.get(edge2.from).add(new Edge(edge2.to, edge2.cost));
            G.get(edge2.to).add(new Edge(edge2.from, edge2.cost));

            cost += edge2.cost;
            numEdges++;
            if (numEdges >= numVertexes - 1) {
                break;
            }
        }
        return cost;
    }

    public int prim() {

        ArrayList> G = new ArrayList<>();
        for (int i = 0; i < numVertexes; i++) {
            G.add(new ArrayList<>());
        }
        for (Edge2 edge2 : edges) {
            G.get(edge2.from).add(new Edge2(edge2.from, edge2.to, edge2.cost));
            G.get(edge2.to).add(new Edge2(edge2.to, edge2.from, edge2.cost));
        }

        int cost = 0;
        int numEdges = 0;

        boolean[] used = new boolean[numVertexes];
        PriorityQueue pq = new PriorityQueue<>(new Comparator() {
            @Override
            public int compare(Edge2 o1, Edge2 o2) {
                if (o1.cost < o2.cost) {
                    return -1;
                }
                if (o1.cost > o2.cost) {
                    return 1;
                }
                return 0;
            }
        });
        {
            int vertex = (int) (numVertexes * Math.random());
            pq.add(new Edge2(vertex, vertex, 0));
        }
        for (; !pq.isEmpty();) {
            Edge2 current = pq.poll();

            if (used[current.to]) {
                continue;
            }

            used[current.to] = true;
            cost += current.cost;

            if (current.from != current.to) {
                numEdges++;
                if (numEdges == numVertexes - 1) {
                    break;
                }

                this.G.get(current.from).add(new Edge(current.to, current.cost));
                this.G.get(current.to).add(new Edge(current.from, current.cost));
            }

            for (Edge2 edge : G.get(current.to)) {
                if (used[edge.to]) {
                    continue;
                }
                pq.add(edge);
            }

        }

        return cost;
    }

}

class Point implements Comparable {

    public int x;
    public int y;

    public Point() {
        this(0, 0);
    }

    public Point(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }

    public Point add(Point point) {
        return new Point(x + point.x, y + point.y);
    }

    public Point subtract(Point point) {
        return new Point(x - point.x, y - point.y);
    }

    public Point multiply(int a) {
        return new Point(a * x, a * y);
    }

    public Point divide(int a) {
        // BigInteger.ONE.divide(val)(val)
        return new Point(x / a, y / a);
    }

    public int cross(Point point) {
        return x * point.y - y * point.x;
    }

    public static int cross(int x, int y, int x2, int y2) {
        return x * y2 - y * x2;
    }

    public Point operator(Point a) {
        return new Point(x * a.x - y * a.y, x * a.y + y * a.x);
    }

    // public boolean operator<(const Point&p)const
    //
    // {
    // return !equals(x, p.x) ? x < p.x : (!equals(y, p.y) && y < p.y);
    // }
    @Override
    public int compareTo(Point o) {
        if (x == o.x) {
            if (y == o.y) {
                return 0;
            } else if (y < o.y) {
                return -1;
            } else {
                return 1;
            }
        } else if (x < o.x) {
            return -1;
        } else {
            return 1;
        }
    }

    // bool operator==(const Point&p)const
    //
    // {
    // return fabs(x - p.x) < EPSILON && fabs(y - p.y) < EPSILON;
    // }

    @Override
    public String toString() {
        // return "Point [x=" + x + ", y=" + y + "]";
        return "(" + x + "," + y + ")";
    }

    private int hash = 0;

    @Override
    public int hashCode() {
        if (hash == 0) {
            final int prime = 31;
            int result = 1;
            result = prime * result + x;
            result = prime * result + y;
            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;
        Point other = (Point) obj;
        if (x != other.x)
            return false;
        if (y != other.y)
            return false;
        return true;
    }

}

class Node implements Comparable {
    Node parent;
    int numCells;
    int r;
    int c;
    double random;

    public Node(Node parent, int r, int c, int numCells) {
        super();
        this.parent = parent;
        this.r = r;
        this.c = c;
        this.numCells = numCells;
        random = RectilinearSteinerTree.rng.nextDouble();
    }

    @Override
    public int compareTo(Node o) {
        if (numCells < o.numCells) {
            return -1;
        }
        if (numCells > o.numCells) {
            return 1;
        }
        if (random < o.random) {
            return -1;
        }
        if (random > o.random) {
            return 1;
        }
        return 0;
    }
}