点の座標を決める問題なので、CirclesSeparation (2013 TCO Marathon Round 3) と同じ問題だと思いました。

シミュレーテッドアニーリングしました。
最後にヒルクライミングしました。

シミュレーテッドアニーリング
  • 遷移確率は random[0,1) < exp(相対誤差/温度)
  • 温度は 0.2 -> 0 に線形に冷ます
  • 近傍の範囲も 128 -> 1 に線形に減らす


近傍

  • 前回選んだ点からつながっている点で最もスコアを悪くしている点を選んで、前回選んだ点を中心に対称の座標に移動する。
  • 前回選んだ点からつながっている点で最もスコアを悪くしている点を選んで、 (1 + random[0,1) *
    近傍の範囲) の8方向で、スコアを最も良くする座標に移動する。
  • 前回選んだ点からつながっている点で最もスコアを悪くしている点を選んで、 {近傍の範囲*1/8, 近傍の範囲*2/8, 近傍の範囲*3/8, 近傍の範囲*4/8, 近傍の範囲*5/8, 近傍の範囲*6/8, 近傍の範囲*7/8, 近傍の範囲*8/8, } * 8方向で、スコアを最も良くする座標に移動する。
  • 前回選んだ点からつながっている点で最もスコアを悪くしている点を選んで、 (1 + random[0,1) *
    近傍の範囲) の8方向の内ランダムに移動する。
  • 前回選んだ点を、数千回に1回、最小レシオまたは最大レシオの辺の4点からランダムに1点選んで、更新する。最小レシオ,最大レシオもいっしょに更新する。
  • スコアは、最小レシオ,最大レシオを覚えておいて、選んだ点の辺のみ計算する。


ヒルクライミング

近傍

  • 改めて計算し直した、最小レシオまたは最大レシオの辺の4点からランダムに1点選んで、8近傍で最も問題のスコアが良くなる座標に移動する。

English(Google Translate)


Since it is a matter of determining the coordinates of the point, I thought it was the same problem as CirclesSeparation (2013 TCO Marathon Round 3).

I simulated annealed.
Finally I did hill climbing.

Simulated annealing

    
The transition probability is random [0, 1) <exp (relative error / temperature)
    
Cool the temperature linearly to 0.2 -> 0
    
Reduce the neighborhood range linearly to 128 -> 1


Neighborhood

    
Choose the point with the worst score at the point connected from the last point chosen, and move to the symmetrical coordinates around the last point chosen.
    
Select the point that has the worst score at the point connected from the last point chosen, and (1 + random [0, 1) *
    
Move to the coordinates that maximize the score in 8 directions of the neighborhood).
    
Select the point that has the worst score at the point connected from the last point chosen, and select {Point in the neighborhood * 1/8, the range in the vicinity * 2/8, the range in the vicinity * 3/8, the range in the vicinity * 4/8, the range of the neighborhood * 5/8, the range of the neighborhood * 6/8, the range of the neighborhood * 7/8, the range of the neighborhood * 8/8,} * Moving.
    
Select the point that has the worst score at the point connected from the last point chosen, and (1 + random [0, 1) *
    
A range in the vicinity) within the eight directions.
    
Select one point at the last time randomly from four points of the minimum ratio or the maximum ratio side once every several thousand times and update it. Update minimum ratio, maximum ratio together.
    
For the score, remember the minimum ratio, the maximum ratio, and calculate only the side of the selected point.



Hill climbing

Neighborhood

    
Randomly select one point from the four points on the minimum ratio or maximum ratio ratio that was recalculated anew and move to the coordinates with the best problem score in 8 neighborhood.



source code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

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

private double score;
private double bestScore;

private Point[] points;
private Edge[] edges;
private byte[][] usedPoint = new byte[size][size];
private Point[] bestPoints;

private double[] pointIndexToScore;
private IntArray[] pointIndexToEdgeIndexes;
private int numVertices;
private int numEdges;

private static final int[] dr = new int[] { -1, -1, -1, 0, 1, 1, 1, 0, };
private static final int[] dc = new int[] { -1, 0, 1, 1, 1, 0, -1, -1, };
private int countUsed = 0;
private int countOutOfRange = 0;

public int[] plot(int numVertices, int[] edgeInformations) {
init(numVertices, edgeInformations);

solve();

int[] solution = makeSolution();

Utils.debug("time", watch.getSecond(), "score", calculateScore(), "countUsed", countUsed, "countOutOfRange", countOutOfRange);
return solution;
}

private void solve() {
points = new Point[numVertices];
for (int pointIndex = 0; pointIndex < points.length; pointIndex++) {
for (;;) {
int r = (int) (size * rng.nextDouble());
int c = (int) (size * rng.nextDouble());
assert usedPoint[r][c] >= 0;
if (usedPoint[r][c] == 0) {
points[pointIndex] = new Point(r, c);
usedPoint[r][c]++;
break;
}
}
}

bestPoints = new Point[numVertices];
for (int i = 0; i < bestPoints.length; i++) {
bestPoints[i] = new Point(0, 0);
}

pointIndexToScore = new double[numVertices];
for (int pointIndex = 0; pointIndex < points.length; pointIndex++) {
pointIndexToScore[pointIndex] = calculateLocalScore(pointIndex);
}

score = calculateScore();

SA();

greedy();
}

private void init(int numVertices, int[] edgeInformations) {
this.numVertices = numVertices;

assert edgeInformations.length % 3 == 0;
this.numEdges = edgeInformations.length / 3;

Utils.debug("numVertices", numVertices, "numEdges", numEdges);

edges = new Edge[numEdges];
for (int i = 0; i < numEdges; i++) {
edges[i] = new Edge(edgeInformations[3 * i + 0], edgeInformations[3 * i + 1], edgeInformations[3 * i + 2]);
}

pointIndexToEdgeIndexes = new IntArray[numVertices];
for (int i = 0; i < pointIndexToEdgeIndexes.length; i++) {
pointIndexToEdgeIndexes[i] = new IntArray(16);
}
for (int i = 0; i < edges.length; i++) {
pointIndexToEdgeIndexes[edges[i].pointIndex1].add(i);
pointIndexToEdgeIndexes[edges[i].pointIndex2].add(i);
}
}

private int[] makeSolution() {
int[] solution = new int[2 * numVertices];
for (int i = 0; i < numVertices; i++) {
solution[2 * i + 0] = points[i].r;
solution[2 * i + 1] = points[i].c;
}
return solution;
}

private void SA() {
double second = 1;
int mask10 = (1 << 10) - 1;
int mask14 = (1 << 14) - 1;
int mask = 1;
{
int n = 1;
while (n < edges.length) {
n <<= 1;
}
mask = n - 1;
}
for (sa.loop = 0;; sa.loop++) {

if ((sa.loop & mask10) == 0) {
if ((sa.loop & mask14) == 0) {
sa.updateTime();

if (sa.isTLE()) {
saveBest();
loadBest();
Utils.debug(sa.loop, String.format("%.2f%%", 100.0 * sa.countChange / sa.loop), String.format("%.2f%%", 100.0 * sa.countAccept / sa.countChange), String.format("%.4f", score), String.format("%.6f", sa.temperature), String.format("%.0f", sa.range), countOutOfRange);
break;
}

sa.updateTemperature();
sa.updateRange();
}

adjustMargins();

if ((sa.loop & mask) == 0) {
pointIndexOfWorstScore();
int edgeIndex = rng.nextDouble() < 0.5 ? minRatioEdgeIndex : maxRatioEdgeIndex;
previousPointIndex = rng.nextDouble() < 0.5 ? edges[edgeIndex].pointIndex1 : edges[edgeIndex].pointIndex2;

saveBest();
}

if (sa.time > second) {
second++;
Utils.debug(sa.loop, String.format("%.2f%%", 100.0 * sa.countChange / sa.loop), String.format("%.2f%%", 100.0 * sa.countAccept / sa.countChange), String.format("%.4f", score), String.format("%.6f", sa.temperature), String.format("%.0f", sa.range), countOutOfRange);
}
}

if (rng.nextDouble() < 0.1) {
selectAPointAndMoveToASymmetricCoordinateForOnePoint();
continue;
}
if (rng.nextDouble() < 0.1) {
selectAPointAndMoveToBestDirection();
continue;
}
if (rng.nextDouble() < 0.01) {
selectAPointAndMoveToBestDirectionAndLength();
continue;
}
selectAPointAndMoveToNearCoordinate();

}
}

private void greedy() {

sa.startTime = 9.5;
sa.endTime = 9.8;
sa.startRange = sa.endRange;
sa.startTemperature = sa.endTemperature;
sa.countChange = 0;
sa.countAccept = 0;
for (sa.loop = 0;; sa.loop++) {

sa.updateTime();

if (sa.isTLE()) {
saveBest();
loadBest();
Utils.debug(sa.loop, String.format("%.2f%%", 100.0 * sa.countChange / sa.loop), String.format("%.2f%%", 100.0 * sa.countAccept / sa.countChange), String.format("%.4f", score), String.format("%.6f", sa.temperature), String.format("%.0f", sa.range), countOutOfRange);
break;
}

adjustMargins();

selectAPointAndMoveToBestDirectionGreedy();
}
}

private int previousPointIndex;

private void selectAPointAndMoveToBestDirection() {
int pointIndex = pointIndexOfLocalWorstScore(previousPointIndex);
previousPointIndex = pointIndex;

int currentR = points[pointIndex].r;
int currentC = points[pointIndex].c;

double currentScore = pointIndexToScore[pointIndex];

int length = (1 + (int) (sa.range * rng.nextDouble()));

double bestScore = -1;
int bestR = -1;
int bestC = -1;

for (int d = 0; d < dr.length; d++) {

int nextR = currentR + length * dr[d];
int nextC = currentC + length * dc[d];

if (nextR < 0) {
nextR = 0;
} else if (nextR >= size) {
nextR = size - 1;
}
if (nextC < 0) {
nextC = 0;
} else if (nextC >= size) {
nextC = size - 1;
}

if (usedPoint[nextR][nextC] > 0) {
countUsed++;
continue;
}

points[pointIndex].r = nextR;
points[pointIndex].c = nextC;

double nextScore = calculateLocalScore(pointIndex);

if (nextScore > bestScore) {
bestScore = nextScore;
bestR = nextR;
bestC = nextC;
}
}

sa.countChange++;
if (bestScore >= currentScore || sa.accept(bestScore, currentScore)) {
sa.countAccept++;

pointIndexToScore[pointIndex] = bestScore;

points[pointIndex].r = bestR;
points[pointIndex].c = bestC;

usedPoint[currentR][currentC]--;
usedPoint[bestR][bestC]++;
} else {
points[pointIndex].r = currentR;
points[pointIndex].c = currentC;
}
}

private void selectAPointAndMoveToBestDirectionGreedy() {
pointIndexOfWorstScore();
int pointIndex = (sa.loop & 1) == 0 ? (rng.nextDouble() < 0.5 ? edges[minRatioEdgeIndex].pointIndex1 : edges[minRatioEdgeIndex].pointIndex2) : (rng.nextDouble() < 0.5 ? edges[maxRatioEdgeIndex].pointIndex1 : edges[maxRatioEdgeIndex].pointIndex2);
previousPointIndex = pointIndex;

int currentR = points[pointIndex].r;
int currentC = points[pointIndex].c;
double currentScore = minRatio / maxRatio;

int length = 1;

double bestScore = -1;
int bestR = -1;
int bestC = -1;

for (int d = 0; d < dr.length; d++) {

int nextR = currentR + length * dr[d];
int nextC = currentC + length * dc[d];

if (nextR < 0 || nextR >= size || nextC < 0 || nextC >= size) {
countOutOfRange++;
continue;
}

if (usedPoint[nextR][nextC] > 0) {
countUsed++;
continue;
}

points[pointIndex].r = nextR;
points[pointIndex].c = nextC;

double nextScore = calculateScore();

if (nextScore > bestScore) {
bestScore = nextScore;
bestR = nextR;
bestC = nextC;
}
}

if (bestR == -1) {
points[pointIndex].r = currentR;
points[pointIndex].c = currentC;
return;
}

sa.countChange++;
if (bestScore > currentScore) {
sa.countAccept++;

points[pointIndex].r = bestR;
points[pointIndex].c = bestC;

usedPoint[currentR][currentC]--;
usedPoint[bestR][bestC]++;

score = bestScore;
saveBestDoNotUpdateScore();
} else {
points[pointIndex].r = currentR;
points[pointIndex].c = currentC;
}
}

private void selectAPointAndMoveToBestDirectionAndLength() {
int pointIndex = pointIndexOfLocalWorstScore(previousPointIndex);
previousPointIndex = pointIndex;

int currentR = points[pointIndex].r;
int currentC = points[pointIndex].c;

double currentScore = pointIndexToScore[pointIndex];

int bestR = -1;
int bestC = -1;

double bestScore = -1;
int bestDirection = -1;
for (int d = 0; d < dr.length; d++) {

int nextR = currentR + dr[d];
int nextC = currentC + dc[d];

if (nextR < 0 || nextR >= size || nextC < 0 || nextC >= size) {
countOutOfRange++;
continue;
}

if (usedPoint[nextR][nextC] > 0) {
countUsed++;
continue;
}

points[pointIndex].r = nextR;
points[pointIndex].c = nextC;

double nextScore = calculateLocalScore(pointIndex);

if (nextScore > bestScore) {
bestScore = nextScore;
bestR = nextR;
bestC = nextC;
bestDirection = d;
}
}

if (bestDirection == -1) {
return;
}

int deltaLength = (int) (Math.ceil(sa.range / 8.0));
for (int i = 0; i < 8; i++) {

int length = i * deltaLength;
int nextR = currentR + length * dr[bestDirection];
int nextC = currentC + length * dc[bestDirection];

if (nextR < 0 || nextR >= size || nextC < 0 || nextC >= size) {
countOutOfRange++;
break;
}

if (usedPoint[nextR][nextC] > 0) {
countUsed++;
continue;
}

points[pointIndex].r = nextR;
points[pointIndex].c = nextC;

double nextScore = calculateLocalScore(pointIndex);

if (nextScore > bestScore) {
bestScore = nextScore;
bestR = nextR;
bestC = nextC;
}
}

sa.countChange++;
if (bestScore >= currentScore || sa.accept(bestScore, currentScore)) {
sa.countAccept++;

pointIndexToScore[pointIndex] = bestScore;

points[pointIndex].r = bestR;
points[pointIndex].c = bestC;

usedPoint[currentR][currentC]--;
usedPoint[bestR][bestC]++;
} else {
points[pointIndex].r = currentR;
points[pointIndex].c = currentC;
}
}

private void selectAPointAndMoveToNearCoordinate() {
int pointIndex = pointIndexOfLocalWorstScore(previousPointIndex);
previousPointIndex = pointIndex;

int currentR = points[pointIndex].r;
int currentC = points[pointIndex].c;

double currentScore = pointIndexToScore[pointIndex];

int direction = (int) (dr.length * rng.nextDouble());
int length = (1 + (int) (sa.range * rng.nextDouble()));
int nextR = currentR + length * dr[direction];
int nextC = currentC + length * dc[direction];

if (nextR < 0 || nextR >= size || nextC < 0 || nextC >= size) {
direction = (direction + (dr.length >>> 1)) % dr.length;
nextR = currentR + length * dr[direction];
nextC = currentC + length * dc[direction];
}

if (nextR < 0) {
nextR = 0;
} else if (nextR >= size) {
nextR = size - 1;
}
if (nextC < 0) {
nextC = 0;
} else if (nextC >= size) {
nextC = size - 1;
}

if (usedPoint[nextR][nextC] > 0) {
countUsed++;
return;
}

points[pointIndex].r = nextR;
points[pointIndex].c = nextC;

double nextScore = calculateLocalScore(pointIndex);

sa.countChange++;
if (nextScore >= currentScore || sa.accept(nextScore, currentScore)) {
sa.countAccept++;

pointIndexToScore[pointIndex] = nextScore;
usedPoint[currentR][currentC]--;
usedPoint[nextR][nextC]++;
} else {
points[pointIndex].r = currentR;
points[pointIndex].c = currentC;
}

}

private void selectAPointAndMoveToASymmetricCoordinateForOnePoint() {
int edgeIndex = edgeIndexOfLocalWorstScore(previousPointIndex);
int pointIndex = edges[edgeIndex].pointIndex1 == previousPointIndex ? edges[edgeIndex].pointIndex2 : edges[edgeIndex].pointIndex1;
int pointIndex2 = edges[edgeIndex].pointIndex1 == previousPointIndex ? edges[edgeIndex].pointIndex1 : edges[edgeIndex].pointIndex2;
assert pointIndex2 == previousPointIndex;
previousPointIndex = pointIndex;

int currentR = points[pointIndex].r;
int currentC = points[pointIndex].c;

double currentScore = pointIndexToScore[pointIndex];

int nextR = points[pointIndex].r + 2 * (points[pointIndex2].r - points[pointIndex].r);
int nextC = points[pointIndex].c + 2 * (points[pointIndex2].c - points[pointIndex].c);

if (nextR < 0) {
nextR = 0;
} else if (nextR >= size) {
nextR = size - 1;
}
if (nextC < 0) {
nextC = 0;
} else if (nextC >= size) {
nextC = size - 1;
}

if (usedPoint[nextR][nextC] > 0) {
countUsed++;
return;
}

points[pointIndex].r = nextR;
points[pointIndex].c = nextC;

double nextScore = calculateLocalScore(pointIndex);

sa.countChange++;
if (nextScore >= currentScore || sa.accept(nextScore, currentScore)) {
sa.countAccept++;

pointIndexToScore[pointIndex] = nextScore;
usedPoint[currentR][currentC]--;
usedPoint[nextR][nextC]++;
} else {
points[pointIndex].r = currentR;
points[pointIndex].c = currentC;
}

}

private double calculateScore() {
double min = 1e99;
double max = -1e99;
for (int i = 0; i < edges.length; i++) {
double ratio = calculateSquaredDistance(edges[i]) * edges[i].inverseSquaredDesiredLength;
min = Math.min(min, ratio);
max = Math.max(max, ratio);
}
return Math.sqrt(min / max);
}

private double minRatio;
private double maxRatio;
private int minRatioEdgeIndex;
private int maxRatioEdgeIndex;

private void pointIndexOfWorstScore() {
double min = 1e99;
int mini = -1;
double max = -1e99;
int maxi = -1;
for (int i = 0; i < edges.length; i++) {
double ratio = calculateSquaredDistance(edges[i]) * edges[i].inverseSquaredDesiredLength;
if (ratio < min) {
min = ratio;
mini = i;
}
if (ratio > max) {
max = ratio;
maxi = i;
}
}
minRatio = Math.sqrt(min);
maxRatio = Math.sqrt(max);
minRatioEdgeIndex = mini;
maxRatioEdgeIndex = maxi;
}

private double calculateLocalScore(int pointIndex) {
double min = 1e99;
double max = -1e99;
for (int i = 0; i < pointIndexToEdgeIndexes[pointIndex].length; i++) {
Edge edge = edges[pointIndexToEdgeIndexes[pointIndex].values[i]];
double ratio = calculateSquaredDistance(edge) * edge.inverseSquaredDesiredLength;
min = Math.min(min, ratio);
max = Math.max(max, ratio);
}
return Math.min(Math.sqrt(min) / maxRatio, minRatio / Math.sqrt(max));
}

private int pointIndexOfLocalWorstScore(int pointIndex) {
double min = 1e99;
int mini = -1;
double max = -1e99;
int maxi = -1;
for (int i = 0; i < pointIndexToEdgeIndexes[pointIndex].length; i++) {
int edgeIndex = pointIndexToEdgeIndexes[pointIndex].values[i];
Edge edge = edges[edgeIndex];
double ratio = calculateSquaredDistance(edge) * edge.inverseSquaredDesiredLength;
if (ratio < min) {
min = ratio;
mini = edgeIndex;
}
if (ratio > max) {
max = ratio;
maxi = edgeIndex;
}
}
return (Math.sqrt(min) / maxRatio < minRatio / Math.sqrt(max) ? (edges[mini].pointIndex1 == pointIndex ? edges[mini].pointIndex2 : edges[mini].pointIndex1) : (edges[maxi].pointIndex1 == pointIndex ? edges[maxi].pointIndex2 : edges[maxi].pointIndex1));
}

private int edgeIndexOfLocalWorstScore(int pointIndex) {
double min = 1e99;
int mini = -1;
double max = -1e99;
int maxi = -1;
for (int i = 0; i < pointIndexToEdgeIndexes[pointIndex].length; i++) {
int edgeIndex = pointIndexToEdgeIndexes[pointIndex].values[i];
Edge edge = edges[edgeIndex];
double ratio = calculateSquaredDistance(edge) * edge.inverseSquaredDesiredLength;
if (ratio < min) {
min = ratio;
mini = edgeIndex;
}
if (ratio > max) {
max = ratio;
maxi = edgeIndex;
}
}
return (Math.sqrt(min) / maxRatio < minRatio / Math.sqrt(max) ? mini : maxi);
}

private double calculateSquaredDistance(Edge edge) {
int dr = points[edge.pointIndex1].r - points[edge.pointIndex2].r;
int dc = points[edge.pointIndex1].c - points[edge.pointIndex2].c;
return (dr * dr + dc * dc);
}

private void loadBest() {
score = bestScore;
for (int i = 0; i < points.length; i++) {
points[i].r = bestPoints[i].r;
points[i].c = bestPoints[i].c;
}
}

private void saveBest() {
score = calculateScore();
if (score > bestScore) {
bestScore = score;
for (int i = 0; i < points.length; i++) {
bestPoints[i].r = points[i].r;
bestPoints[i].c = points[i].c;
}
}
}

private void saveBestDoNotUpdateScore() {
if (score > bestScore) {
bestScore = score;
for (int i = 0; i < points.length; i++) {
bestPoints[i].r = points[i].r;
bestPoints[i].c = points[i].c;
}
}
}

private void adjustMargins() {
int minR = (int) 1e9;
int maxR = (int) -1e9;
int minC = (int) 1e9;
int maxC = (int) -1e9;
for (int i = 0; i < points.length; i++) {
minR = Math.min(minR, points[i].r);
maxR = Math.max(maxR, points[i].r);
minC = Math.min(minC, points[i].c);
maxC = Math.max(maxC, points[i].c);
}

int marginL = minC - 0;
int marginR = 700 - maxC;
int marginD = minR - 0;
int marginU = 700 - maxR;

int newMarginD = (marginD + marginU) / 2;
int deltaR = newMarginD - marginD;
int newMarginL = (marginL + marginR) / 2;
int deltaC = newMarginL - marginL;

for (int i = 0; i < points.length; i++) {
usedPoint[points[i].r][points[i].c]--;
points[i].r += deltaR;
points[i].c += deltaC;
usedPoint[points[i].r][points[i].c]++;
}

}

public static void main(String[] args) {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

int N = Integer.parseInt(br.readLine());
int E = Integer.parseInt(br.readLine());
int[] edges = new int[E];
for (int i = 0; i < E; ++i) {
edges[i] = Integer.parseInt(br.readLine());
}

GraphDrawing gd = new GraphDrawing();
int[] ret = gd.plot(N, edges);

System.out.println(ret.length);
for (int i = 0; i < ret.length; ++i) {
System.out.println(ret[i]);
}
System.out.flush();
} catch (Exception e) {
e.printStackTrace();
}
}
}

class Point {
int r;
int c;

public Point(int r, int c) {
this.r = r;
this.c = c;
}
}

class Edge {
int pointIndex1;
int pointIndex2;
double inverseSquaredDesiredLength;

public Edge(int pointIndex1, int pointIndex2, int desiredLength) {
super();
this.pointIndex1 = pointIndex1;
this.pointIndex2 = pointIndex2;
this.inverseSquaredDesiredLength = 1.0 / (desiredLength * desiredLength);
}

@Override
public String toString() {
return "[" + pointIndex1 + "," + pointIndex2 + "]";
}

}

class SAState {

public static final boolean useTime = true;

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

public double startTemperature = 2 * 1e-1;
public double endTemperature = 0;
public double temperature = startTemperature;

public double startRange = 128;
public double endRange = 1;
public double range = startRange;

public int loop;
public int countChange;
public int countAccept;

public void updateTemperature() {
temperature = 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 ? GraphDrawing.watch.getSecond() : loop;
}

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

public boolean accept(double newScore, double currentScore) {
assert newScore - currentScore < 0;
assert temperature >= 0;
return GraphDrawing.rng.nextDouble() < StrictMath.exp((newScore - currentScore) / (currentScore * temperature));
}
}

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 IntArray {
public int[] values;
public int length;

public IntArray() {
this(new int[4], 0);
}

public IntArray(int capacity) {
this(new int[capacity], 0);
}

public IntArray(int[] values) {
this(values, values.length);
}

public IntArray(int[] values, int length) {
this.values = values;
this.length = length;
}

public void add(int value) {
if (length == values.length) {
values = Arrays.copyOf(values, values.length << 1);
}
values[length++] = value;
}

public int remove() {
return values[--length];
}

public boolean contains(int value) {
for (int i = 0; i < length; i++) {
if (values[i] == value) {
return true;
}
}
return false;
}

public void clear() {
length = 0;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("{");
for (int i = 0; i < length; i++) {
sb.append(values[i] + ",");
}
sb.append("}");
return sb.toString();
}

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

public int remove(int index) {
if (index >= length) {
throw new AssertionError();
}

if (index == length - 1) {
return remove();
}

int res = values[index];
System.arraycopy(values, index + 1, values, index, length - (index + 1));
length--;

return res;
}

public void set(int index, int value) {
if (index >= length) {
throw new AssertionError();
}

if (length >= values.length - 1) {
values = Arrays.copyOf(values, values.length << 1);
}
System.arraycopy(values, index, values, index + 1, length - index);
length++;

values[index] = value;
}

public IntArray copy() {
return new IntArray(Arrays.copyOf(values, length), length);
}

public int[] toArray() {
return Arrays.copyOf(values, length);
}

}