Rank 暫定30位くらい


Approach

  • submission1
    • Approach : ジャンクション無しで MST
    • 同点で並んでいるところに混ざりたかったのに失敗した。
  • submission2
    • Score : 0.5%ほど改善
    • Approach : SA
    • 近傍 : ジャンクションを加える、外す
    • 複数の点の位置を決める問題なのでSAでいいでしょう。
  • submission3
    • Score : 0.1%ほど改善
    • Approach : SA
    • Kruskalの高速化 : 都市x都市の辺を並べ替えて覚えておく。計算するときに、都市xジャンクションとジャンクションxジャンクションの辺を生成して、並べ替えて、 マージソートのようにして、距離の短い辺を取り出す。
    • スコアの近似 : 使えるジャンクションはランダムに選ばれるので、期待値を使いたい。でも遅いので近似することにする。期待値の近似 : ジャンクションのコスト*ジャンクション数 + ジャンクション無しのMST + (1 - ジャンクションの失敗率) * (ジャンクション有りのMST - ジャンクション無しのMST)
    • スコアの近似は最小二乗法(特徴は{ジャンクションコスト、失敗率、S、都市数、ジャンクション数、ジャンクション無しのMST、ジャンクション有りのMST、ジャンクションコスト*失敗率、ジャンクションコスト*S、...、ジャンクション無しのMST*ジャンクション有りのMST})も使ったけど、ほぼ同じ式になった。
  • submission4
    • Score : 0.05%ほど改善
    • Approach : SA
    • 近傍 : ジャンクションを加える、外す、移動する
  • submission5
    • Score : 0.05%ほど改善
    • Approach : SA
    • Kruskalの高速化 : 都市x都市の辺を並べ替えて覚えておく。使わない辺を除くいておく。


source code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class RoadsAndJunctions {
	private int numCities;
	private Point[] cities;
	private double junctionCost;
	private double failureProbability;
	private int S;

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

	private double score;
	private int numJunctions;
	private Point[] junctions;

	private double bestScore;
	private int numBestJunctions;
	private Point[] bestJunctions;

	private UnionFind unionFind;

	private Comparator comparator = 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;
		}
	};

	private int numEdges;
	private Edge2[] edges;
	private int numNewEdges;
	private Edge2[] newEdges;
	private double baseScore;
	private double time;

	public int[] buildJunctions(int S, int[] cities, double junctionCost, double failureProbability) {
		init(S, cities, junctionCost, failureProbability);
		solve();
		int[] makeSolution = makeSolution();
		time = watch.getSecond();
		Utils.debug("score", score, "time", time);
		return makeSolution;
	}

	private void init(int S, int[] cities, double junctionCost, double failureProbability) {
		watch.init();

		this.S = S;

		numCities = cities.length / 2;
		this.cities = new Point[numCities];
		for (int i = 0; i < this.cities.length; i++) {
			this.cities[i] = new Point(cities[2 * i + 1], cities[2 * i + 0]);
		}

		this.junctionCost = junctionCost;
		this.failureProbability = failureProbability;

		numJunctions = 0;
		junctions = new Point[2 * numCities];
		for (int i = 0; i < junctions.length; i++) {
			junctions[i] = new Point(0, 0);
		}
		numBestJunctions = 0;
		bestJunctions = new Point[2 * numCities];
		for (int i = 0; i < bestJunctions.length; i++) {
			bestJunctions[i] = new Point(0, 0);
		}

		edges = new Edge2[3 * numCities * 3 * numCities];
		for (int i = 0; i < edges.length; i++) {
			edges[i] = new Edge2(0, 0, 0);
		}
		newEdges = new Edge2[3 * numCities * 3 * numCities];
		for (int i = 0; i < newEdges.length; i++) {
			newEdges[i] = new Edge2(0, 0, 0);
		}

		for (int from = 0; from < numCities; from++) {
			for (int to = from + 1; to < numCities; to++) {
				edges[numEdges].from = from;
				edges[numEdges].to = to;
				edges[numEdges].cost = distance(from, to);
				numEdges++;
			}
		}
		Arrays.sort(edges, 0, numEdges, comparator);

		unionFind = new UnionFind(2 * numCities);

		{
			unionFind.init(numCities);

			double cost = 0;
			int numEdges2 = 0;
			for (int i = 0; i < numEdges; i++) {
				Edge2 edge2 = edges[i];

				if (unionFind.isSame(edge2.from, edge2.to)) {
					for (int j = i; j < numEdges - 1; j++) {
						edges[j] = edges[j + 1];
					}
					numEdges--;
					i--;
					continue;
				}
				unionFind.unite(edge2.from, edge2.to);

				cost += edge2.cost;
				numEdges2++;
				if (numEdges2 >= numCities - 1) {
					numEdges = i + 1;
					break;
				}

			}
			assert numEdges == numEdges2;
			score = cost;
		}
		baseScore = score;

		bestScore = 1e9;
		saveBest();

		Utils.debug("S", S, "numCities", numCities, "cost", String.format("%.1f", junctionCost), "probability", String.format("%.1f%%", 100.0 * failureProbability));
	}

	private double kruskal(Point[] junctions, int numJunctions) {
		int numVertexes = numCities + numJunctions;

		unionFind.init(numVertexes);
		numNewEdges = 0;
		for (int from = numCities; from < numCities + numJunctions; from++) {
			for (int to = 0; to < from; to++) {
				double cost = distance(from, to);
				if (cost <= edges[numEdges - 1].cost) {
					newEdges[numNewEdges].from = from;
					newEdges[numNewEdges].to = to;
					newEdges[numNewEdges].cost = cost;
					numNewEdges++;
				}
			}
		}
		Arrays.sort(newEdges, 0, numNewEdges, comparator);

		double cost = 0;
		int numEdges = 0;
		for (int i = 0, i2 = 0; i < this.numEdges || i2 < numNewEdges;) {
			Edge2 edge2;
			if (i >= this.numEdges) {
				edge2 = newEdges[i2++];
			} else if (i2 >= numNewEdges) {
				edge2 = edges[i++];
			} else if (edges[i].cost <= newEdges[i2].cost) {
				edge2 = edges[i++];
			} else {
				edge2 = newEdges[i2++];
			}

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

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

		return cost;
	}

	private void solve() {
		SA();
		sortJunctions();
	}

	private void sortJunctions() {
		MinimumSpanningTree mst = new MinimumSpanningTree(numCities + numJunctions);
		for (int from = 0; from < numCities + numJunctions; from++) {
			for (int to = from + 1; to < numCities + numJunctions; to++) {
				mst.addEdge(from, to, distance(from, to));
			}
		}
		mst.kruskal();

		ArrayList> hashAndPointPairs = new ArrayList<>();
		for (int from = numCities; from < numCities + numJunctions; from++) {
			ArrayList edges = mst.G.get(from);
			int[] indexes = new int[edges.size()];
			for (int i = 0; i < indexes.length; i++) {
				indexes[i] = edges.get(i).to;
			}
			Arrays.sort(indexes);
			int hashCode = hashCode(indexes);
			hashAndPointPairs.add(new Pair<>(hashCode, new Point(junctions[from - numCities].r, junctions[from - numCities].c)));
		}
		Collections.sort(hashAndPointPairs);

		numJunctions = 0;
		for (Pair pair : hashAndPointPairs) {
			junctions[numJunctions].r = pair.second.r;
			junctions[numJunctions].c = pair.second.c;
			numJunctions++;
		}

	}

	private int hashCode(int a[]) {
		int result = 1;
		for (int element : a) {
			result = 131 * result + element;
		}
		return result;
	}

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

		sa.startTime = watch.getSecond();
		sa.endTime = 9.5;
		sa.init();
		for (;; sa.numIterations++) {
			if ((sa.numIterations & ((1 << 8) - 1)) == 0) {
				sa.update();

				if (sa.isTLE()) {
					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("%7.2f", score), String.format("%7.2f", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
					Utils.debug("score", score, "" + (score - numJunctions * junctionCost) + " + " + junctionCost + " * " + numJunctions + "");
					break;
				}

				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("%7.2f", score), String.format("%7.2f", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
				}
			}

			mutate();
		}
	}

	private void mutate() {
		int random = (int) (3 * rng.nextDouble());
		if (random == 0) {
			add();
		} else if (random == 1) {
			remove();
		} else if (random == 2) {
			move();
		}
	}

	private void add() {
		if (numJunctions >= 2 * numCities) {
			return;
		}
		int r = (int) (S * rng.nextDouble());
		int c = (int) (S * rng.nextDouble());
		junctions[numJunctions].r = r;
		junctions[numJunctions].c = c;
		numJunctions++;

		double deltaScore = calculateApproximateExpectedScore() - score;
		if (sa.accept(deltaScore)) {
			score += deltaScore;
			saveBest();
		} else {
			numJunctions--;
		}
	}

	private void remove() {
		if (numJunctions == 0) {
			return;
		}

		int index = (int) (numJunctions * rng.nextDouble());
		{
			Point swap = junctions[index];
			junctions[index] = junctions[numJunctions - 1];
			junctions[numJunctions - 1] = swap;
		}

		numJunctions--;
		double deltaScore = calculateApproximateExpectedScore() - score;

		if (sa.accept(deltaScore)) {
			score += deltaScore;
			saveBest();
		} else {
			numJunctions++;
		}
	}

	private void move() {
		if (numJunctions == 0) {
			return;
		}

		Point point = junctions[(int) (numJunctions * rng.nextDouble())];

		int currentR = point.r;
		int currentC = point.c;

		point.r += -(int) (0.5 * sa.range) + (sa.range * rng.nextDouble());
		point.c += -(int) (0.5 * sa.range) + (sa.range * rng.nextDouble());

		double deltaScore = calculateApproximateExpectedScore() - score;

		if (sa.accept(deltaScore)) {
			score += deltaScore;
			saveBest();
		} else {
			point.r = currentR;
			point.c = currentC;
		}
	}

	private double calculateApproximateExpectedScore() {
		double score = kruskal(junctions, numJunctions);
		return junctionCost * numJunctions + baseScore + (1.0 - failureProbability) * (score - baseScore);
	}

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

	public int[] buildRoads(int[] junctionStatus) {
		watch.init();

		int validJunctions = 0;
		boolean[] canUse = new boolean[junctionStatus.length];
		for (int i = 0; i < canUse.length; i++) {
			canUse[i] = junctionStatus[i] == 1;
			if (canUse[i]) {
				validJunctions++;
			}
		}

		Utils.debug("validJunctions", validJunctions, "numJunctions", numJunctions);

		MinimumSpanningTree mst = new MinimumSpanningTree(numCities + numJunctions);
		for (int from = 0; from < numCities; from++) {
			for (int to = from + 1; to < numCities; to++) {
				mst.addEdge(from, to, distance(from, to));
			}
			for (int to = numCities; to < numCities + numJunctions; to++) {
				if (!canUse[to - numCities]) {
					continue;
				}
				mst.addEdge(from, to, distance(from, to));
			}
		}
		for (int from = numCities; from < numCities + numJunctions; from++) {
			if (!canUse[from - numCities]) {
				continue;
			}
			for (int to = from + 1; to < numCities + numJunctions; to++) {
				if (!canUse[to - numCities]) {
					continue;
				}
				mst.addEdge(from, to, distance(from, to));
			}
		}

		score = mst.kruskal();
		Utils.debug("score", score + numJunctions * junctionCost, "" + score + " + " + junctionCost + " * " + numJunctions + "");
		score += junctionCost * numJunctions;

		int[] ret = new int[2 * (numCities + validJunctions - 1)];
		int reti = 0;

		LinkedList queue = new LinkedList<>();
		boolean[] used = new boolean[numCities + numJunctions];
		{
			int current = 0;
			queue.add(current);
			used[current] = true;
		}
		for (; !queue.isEmpty();) {
			int current = queue.poll().intValue();
			ArrayList edges = mst.G.get(current);
			for (int i = 0; i < edges.size(); i++) {
				int next = edges.get(i).to;
				if (used[next]) {
					continue;
				}
				used[next] = true;
				queue.add(next);
				ret[2 * reti + 0] = current;
				ret[2 * reti + 1] = next;
				reti++;
			}
		}

		time += watch.getSecond();
		Utils.debug("score", score, "time", time);
		return ret;
	}

	private double distance(int from, int to) {
		int dr = getR(from) - getR(to);
		int dc = getC(from) - getC(to);
		return Math.sqrt(dr * dr + dc * dc);
	}

	private double distance(Point from, Point to) {
		int dr = from.r - to.r;
		int dc = from.c - to.c;
		return Math.sqrt(dr * dr + dc * dc);
	}

	private Point getPoint(int index) {
		return index < numCities ? cities[index] : junctions[index - numCities];
	}

	private int getR(int index) {
		return getPoint(index).r;
	}

	private int getC(int index) {
		return getPoint(index).c;
	}

	private void saveBest() {
		if (score < bestScore) {
			bestScore = score;
			numBestJunctions = 0;
			for (int i = 0; i < numJunctions; i++) {
				bestJunctions[numBestJunctions].r = junctions[i].r;
				bestJunctions[numBestJunctions].c = junctions[i].c;
				numBestJunctions++;
			}
		}
	}

	private void loadBest() {
		score = bestScore;
		numJunctions = 0;
		for (int i = 0; i < numBestJunctions; i++) {
			junctions[numJunctions].r = bestJunctions[i].r;
			junctions[numJunctions].c = bestJunctions[i].c;
			numJunctions++;
		}
	}

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

			int S = Integer.parseInt(br.readLine());
			int C = Integer.parseInt(br.readLine());
			int[] cities = new int[C];
			for (int i = 0; i < C; ++i) {
				cities[i] = Integer.parseInt(br.readLine());
			}
			double junctionCost = Double.parseDouble(br.readLine());
			double failureProbability = Double.parseDouble(br.readLine());

			RoadsAndJunctions rj = new RoadsAndJunctions();
			int[] ret = rj.buildJunctions(S, cities, junctionCost, failureProbability);
			System.out.println(ret.length);
			for (int i = 0; i < ret.length; ++i) {
				System.out.println(ret[i]);
			}
			System.out.flush();

			int J = Integer.parseInt(br.readLine());
			int[] junctionStatus = new int[J];
			for (int i = 0; i < J; ++i) {
				junctionStatus[i] = Integer.parseInt(br.readLine());
			}
			ret = rj.buildRoads(junctionStatus);
			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;
	}

	public boolean equals(Point other) {
		return (r == other.r && c == other.c);
	}

	public int dist2(Point other) {
		return (r - other.r) * (r - other.r) + (c - other.c) * (c - other.c);
	}

}

class MinimumSpanningTree {

	private static final int INF = (int) 1e9;
	ArrayList> G;
	private ArrayList edges;
	private int numVertexes;

	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();
	}

	public void addEdge(int from, int to, double cost) {
		assert cost >= 0;
		assert cost <= INF;
		edges.add(new Edge2(from, to, cost));
	}

	public double kruskal() {
		UnionFind unionFind = new UnionFind(numVertexes);
		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;
			}
		});

		double 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 Edge {
	int to;
	double cost;

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

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

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

class SAState {

	public static final boolean useTime = true;

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

	public double startTemperature = 1;
	public double endTemperature = 0;
	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 void init() {
		numIterations = 0;
		validIterations = 0;
		acceptIterations = 0;

		startTime = useTime ? RoadsAndJunctions.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 ? RoadsAndJunctions.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 (RoadsAndJunctions.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 (RoadsAndJunctions.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 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, S> implements Comparable> {
	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 other = (Pair) 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 o) {
		return first.compareTo(o.first);
	}
}