Approach SAしました。


初期解は、下の図のように、斜めの直線が交差する形に配置しただけ。
Screenshot from 2017-12-13 00-49-24

近傍

初期解の形を維持するようにした。
  1. 2つの領域を交換する。
  2. 領域の長さを変える。短(長)くしたら、直線上の隣が長(短)くなる。
  3. 1つの領域を取り除いて(直線上の隣の領域にして)、別の領域を2つに分けて、どちらかに移る。

試行回数は1千万~5千万回。


source code

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

public class Main {
private static final int[] dr8 = new int[] { 0, -1, -1, -1, 0, 1, 1, 1, };
private static final int[] dc8 = new int[] { -1, -1, 0, 1, 1, 1, 0, -1, };

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

private static final int EMPTY = (1 << 10) - 1;

private int NV;
private int S0;
private int S;

private IntArray[] connectedVs;
private IntArray[] connectedVsEmb;

private boolean[][] isConnected;
private int[][] isConnectedEmb;
private int[][] inverseEmb;

private int score;
private int bestScore = (int) -1e9;
private int scoreBase = 5000;
private int scoreAdd = 0;
private int scoreBonus = 0;
private int scoreLoss = 0;

private int sumScores() {
return scoreBase + scoreAdd + scoreBonus - scoreLoss;
}

private IntArray[] embVSets;
private int preservedEdges;
private int NE;

private String[] run(int NV, int NE, int[] u, int[] v, int NEmbV, int NEmbE, int[] a, int[] b) {
init(NV, NE, u, v, NEmbV, NEmbE, a, b);
solve();
String[] solution = makeSolution();
return solution;
}

private void init(int NV, int NE, int[] u, int[] v, int NEmbV, int NEmbE, int[] a, int[] b) {
this.NV = NV;
this.NE = NE;

for (int i = 0; i < u.length; i++) {
u[i]--;
}
for (int i = 0; i < v.length; i++) {
v[i]--;
}

preservedEdges = 0;
this.isConnected = new boolean[NV][NV];
for (int i = 0; i < u.length; i++) {
isConnected[u[i]][v[i]] = true;
isConnected[v[i]][u[i]] = true;
}

connectedVs = new IntArray[NV];
for (int i = 0; i < connectedVs.length; i++) {
connectedVs[i] = new IntArray(1 << 9);
}
for (int i = 0; i < u.length; i++) {
connectedVs[u[i]].add(v[i]);
connectedVs[v[i]].add(u[i]);
}
this.isConnectedEmb = new int[NV][NV];
for (int i = 0; i < NV; i++) {
Arrays.fill(isConnectedEmb[i], -1);
}
connectedVsEmb = new IntArray[NV];
for (int i = 0; i < connectedVsEmb.length; i++) {
connectedVsEmb[i] = new IntArray(1 << 9);
}
for (int i = 0; i < a.length; i++) {
a[i]--;
}
for (int i = 0; i < b.length; i++) {
b[i]--;
}

S0 = (int) Math.sqrt(NEmbV + 1e-9);
S = S0;
if (S >= NV) {
S = NV;
}
embVSets = new IntArray[NV];
for (int i = 0; i < embVSets.length; i++) {
embVSets[i] = new IntArray(1 << 9);
}
bestEmbVSets = new IntArray[NV];
for (int i = 0; i < bestEmbVSets.length; i++) {
bestEmbVSets[i] = new IntArray(1 << 9);
}

inverseEmb = new int[S][S];
for (int r = 0; r < S; r++) {
for (int c = 0; c < S; c++) {
inverseEmb[r][c] = EMPTY;
}
}

scoreLoss -= NV;
}

private void solve() {

greedy();

score = scoreAdd;
saveBest();
SA();
}

private void greedy() {

int v = 0;
int usedPoints = 0;
for (int r = 0; r < S; r++) {

if (v >= NV) {
break;
}

int length = (S * S - usedPoints) / (NV - v);

for (int c = 0; c < S; c++) {
if (inverseEmb[r][c] != EMPTY) {
continue;
}

int r2 = r;
int c2 = c;
for (int l = 0; l < length; l++) {
if (inverseEmb[r2][c2] != EMPTY) {
break;
}

if (v >= NV) {
int r3;
int c3;
if (isLowerRightDirection(r2, c2)) {
r3 = r2 - dr8[5];
c3 = c2 - dc8[5];
} else {
r3 = r2 - dr8[7];
c3 = c2 - dc8[7];
}
if (!isValid(r3, 0, S)) {
break;
}
if (!isValid(c3, 0, S)) {
if (c3 < 0) {
c3 = 0;
} else if (c3 >= S) {
c3 = S - 1;
}
}
add(toEmbV(r2, c2), inverseEmb[r3][c3]);
} else {
add(toEmbV(r2, c2), v);
}
usedPoints++;

if (isLowerRightDirection(r2, c2)) {
r2 += dr8[5];
c2 += dc8[5];
} else {
r2 += dr8[7];
c2 += dc8[7];
}

if (!isValid(r2, 0, S)) {
break;
} else if (!isValid(c2, 0, S)) {
if (c2 < 0) {
c2 = 0;
} else if (c2 >= S) {
c2 = S - 1;
}
}
}

v++;
}
}

}

private boolean isLowerRightDirection(int r2, int c2) {
return (r2 + c2) % 2 == 0;
}

private boolean add(int embV, int v) {
int embR = toEmbR(embV);
int embC = toEmbC(embV);
assert inverseEmb[embR][embC] == EMPTY;
assert checkCanAdd(v, embR, embC);

inverseEmb[embR][embC] = v;
embVSets[v].add(embV);
scoreLoss++;
for (int d = 0; d < dr8.length; d++) {
int embNextR = embR + dr8[d];
int embNextC = embC + dc8[d];
if (!isValid(embNextR, 0, S)) {
continue;
}
if (!isValid(embNextC, 0, S)) {
continue;
}
if (inverseEmb[embNextR][embNextC] == EMPTY) {
continue;
}
int nextV = inverseEmb[embNextR][embNextC];
assert nextV >= 0 && nextV < NV;
if (!isConnected[nextV][v]) {
continue;
}
if (isConnectedEmb[nextV][v] >= 0) {
continue;
}

isConnectedEmb[v][nextV] = connectedVsEmb[v].length;
connectedVsEmb[v].add(nextV);

isConnectedEmb[nextV][v] = connectedVsEmb[nextV].length;
connectedVsEmb[nextV].add(v);
scoreAdd += 100;
preservedEdges++;
if (preservedEdges == NE) {
scoreBonus += 100000;
}

}
return true;
}

private boolean adds(int[] embVs, int start, int end, int v) {
for (int i = start; i < end; i++) {
int embV = embVs[i];
int embR = toEmbR(embV);
int embC = toEmbC(embV);
assert inverseEmb[embR][embC] == EMPTY;
inverseEmb[embR][embC] = v;
embVSets[v].add(embV);
scoreLoss++;
for (int d = 0; d < dr8.length; d++) {
int embNextR = embR + dr8[d];
int embNextC = embC + dc8[d];
if (!isValid(embNextR, 0, S)) {
continue;
}
if (!isValid(embNextC, 0, S)) {
continue;
}
if (inverseEmb[embNextR][embNextC] == EMPTY) {
continue;
}
int nextV = inverseEmb[embNextR][embNextC];
assert nextV >= 0 && nextV < NV;
if (!isConnected[v][nextV]) {
continue;
}
if (isConnectedEmb[v][nextV] >= 0) {
continue;
}
isConnectedEmb[v][nextV] = connectedVsEmb[v].length;
connectedVsEmb[v].add(nextV);
isConnectedEmb[nextV][v] = connectedVsEmb[nextV].length;
connectedVsEmb[nextV].add(v);
scoreAdd += 100;
preservedEdges++;
if (preservedEdges == NE) {
scoreBonus += 100000;
}
}
}
return true;
}

private IntArray change = new IntArray();

private int simulateAdds(int[] embVs, int start, int end, int v) {
countUsed++;

update(embVs, start, end, v);

int score = 0;

for (int i = start; i < end; i++) {
int embV = embVs[i];
int embR = toEmbR(embV);
int embC = toEmbC(embV);
for (int d = 0; d < dr8.length; d++) {
int embNextR = embR + dr8[d];
int embNextC = embC + dc8[d];
if (!isValid(embNextR, 0, S)) {
continue;
}
if (!isValid(embNextC, 0, S)) {
continue;
}
if (inverseEmb[embNextR][embNextC] == EMPTY) {
continue;
}
int nextV = inverseEmb[embNextR][embNextC];
assert nextV >= 0 && nextV < NV;
if (!isConnected[nextV][v]) {
continue;
}

if (used[nextV] == countUsed) {
continue;
}
used[nextV] = countUsed;
score += 100;
}
}
return score;

}

private void update(int[] embVs, int start, int end, int v) {
for (int i = start; i < end; i++) {
int embV = embVs[i];
int embR = toEmbR(embV);
int embC = toEmbC(embV);
change.add((embR << 20) | (embC << 10) | (inverseEmb[embR][embC]));
inverseEmb[embR][embC] = v;
}
}

private boolean checkCanAdd(int v, int embR, int embC) {
boolean b = embVSets[v].length == 0;
boolean b2 = false;
if (!b) {
for (int d = 0; d < dr8.length; d++) {
int embNextR = embR + dr8[d];
int embNextC = embC + dc8[d];
if (!isValid(embNextR, 0, S)) {
continue;
}
if (!isValid(embNextC, 0, S)) {
continue;
}
if (inverseEmb[embNextR][embNextC] == EMPTY) {
continue;
}
int nextV = inverseEmb[embNextR][embNextC];
if (nextV == v) {
b2 = true;
break;
}
}
}
boolean b3 = b || b2;
return b3;
}

private boolean removeAll(int v) {

for (int i = 0; i < embVSets[v].length; i++) {
int embV = embVSets[v].values[i];

int embR = toEmbR(embV);
int embC = toEmbC(embV);
inverseEmb[embR][embC] = EMPTY;

}
scoreLoss -= embVSets[v].length;
embVSets[v].clear();

for (int i = connectedVsEmb[v].length - 1; i >= 0; i--) {
int nextV = connectedVsEmb[v].values[i];
remove(v, nextV);
remove(nextV, v);
scoreAdd -= 100;
preservedEdges--;
if (preservedEdges + 1 == NE) {
scoreBonus -= 100000;
}
}
return true;

}

private void remove(int v, int nextV) {
int index = isConnectedEmb[v][nextV];
IntArray vs = connectedVsEmb[v];
if (index != vs.length - 1) {
int otherV = vs.values[vs.length - 1];
vs.values[vs.length - 1] = vs.values[index];
vs.values[index] = otherV;
isConnectedEmb[v][otherV] = index;
}
vs.remove();
isConnectedEmb[v][nextV] = -1;
}

private int[] used = new int[1 << 9];
private int countUsed = 0;
private SAState sa = new SAState();

private void SA() {
int mask = (1 << 10) - 1;

sa.init();
for (;; sa.loop++) {
if ((sa.loop & mask) == 0) {
sa.updateTime();

if (sa.isTLE()) {
loadBest();
break;
}

sa.updateTemperature();
}

change();
}
}

private void change() {
int random = (int) (3 * rng.nextDouble());
if (random == 0) {
swap();
} else if (random == 1) {
changeLength();
} else {
moveLine();
}
}

private IntArray embVs1 = new IntArray();
private IntArray embVs2 = new IntArray();
private IntArray embVs3 = new IntArray();

private void moveLine() {
int v = (int) (NV * rng.nextDouble());

boolean isUpper = rng.nextDouble() < 0.5;

int embV0;
{
assert checkOrder(v);
IntArray embVSet = embVSets[v];
embV0 = embVSet.values[isUpper ? 0 : embVSet.length - 1];
int embR0 = toEmbR(embV0);
if (embR0 == 0) {
isUpper = false;
embV0 = embVSet.values[isUpper ? 0 : embVSet.length - 1];
} else if (embR0 == S - 1) {
isUpper = true;
embV0 = embVSet.values[isUpper ? 0 : embVSet.length - 1];
}
}

int sameLineV = EMPTY;
int embR0 = toEmbR(embV0);
int embC0 = toEmbC(embV0);
if (isLowerRightDirection(embR0, embC0)) {
if (isUpper) {
int r1 = embR0 + dr8[1];
int c1 = embC0 + dc8[1];
if (c1 < 0) {
c1 = 0;
} else if (c1 >= S) {
c1 = S - 1;
}
if (isValid(r1, 0, S)) {
assert inverseEmb[r1][c1] != v;
assert inverseEmb[r1][c1] != EMPTY;
sameLineV = inverseEmb[r1][c1];
}
} else {
int r5 = embR0 + dr8[5];
int c5 = embC0 + dc8[5];
if (c5 < 0) {
c5 = 0;
} else if (c5 >= S) {
c5 = S - 1;
}
if (isValid(r5, 0, S)) {
assert inverseEmb[r5][c5] != v;
assert inverseEmb[r5][c5] != EMPTY;
sameLineV = inverseEmb[r5][c5];
}
}
} else {
if (isUpper) {
int r3 = embR0 + dr8[3];
int c3 = embC0 + dc8[3];
if (c3 < 0) {
c3 = 0;
} else if (c3 >= S) {
c3 = S - 1;
}
if (isValid(r3, 0, S)) {
assert inverseEmb[r3][c3] != v;
assert inverseEmb[r3][c3] != EMPTY;
sameLineV = inverseEmb[r3][c3];
}
} else {
int r7 = embR0 + dr8[7];
int c7 = embC0 + dc8[7];
if (c7 < 0) {
c7 = 0;
} else if (c7 >= S) {
c7 = S - 1;
}
if (isValid(r7, 0, S)) {
assert inverseEmb[r7][c7] != v;
assert inverseEmb[r7][c7] != EMPTY;
sameLineV = inverseEmb[r7][c7];
}
}
}

if (sameLineV == EMPTY) {
return;
}

int toV = (int) (NV * rng.nextDouble());
for (int k = 0; k < NV; k++) {
if (toV == v || toV == sameLineV || embVSets[toV].length <= 1) {
toV = (int) (NV * rng.nextDouble());
} else {
break;
}
}
if (toV == v || toV == sameLineV || embVSets[toV].length <= 1) {
return;
}

int currentLengthToV = embVSets[toV].length;
boolean vIsUpperAtToV = rng.nextDouble() < 0.5;

if (isUpper) {
embVs1.clear();
for (int i = 0; i < embVSets[sameLineV].length; i++) {
embVs1.add(embVSets[sameLineV].values[i]);
}
for (int i = 0; i < embVSets[v].length; i++) {
embVs1.add(embVSets[v].values[i]);
}
} else {
embVs1.clear();
for (int i = 0; i < embVSets[v].length; i++) {
embVs1.add(embVSets[v].values[i]);
}
for (int i = 0; i < embVSets[sameLineV].length; i++) {
embVs1.add(embVSets[sameLineV].values[i]);
}
}
embVs3.clear();
for (int i = 0; i < embVSets[toV].length; i++) {
embVs3.add(embVSets[toV].values[i]);
}

int newLengthV = 1 + (int) ((currentLengthToV - 1) * rng.nextDouble());
int newLengthToV = currentLengthToV - newLengthV;
assert newLengthV > 0;
assert newLengthToV > 0;

int beforeV = -100 * connectedVsEmb[v].length;
int beforeSameLineV = -100 * connectedVsEmb[sameLineV].length;
if (isConnectedEmb[sameLineV][v] >= 0) {
beforeSameLineV += 100;
}
int beforeToV = -100 * connectedVsEmb[toV].length;
if (isConnectedEmb[toV][v] >= 0) {
beforeToV += 100;
}
if (isConnectedEmb[toV][sameLineV] >= 0) {
beforeToV += 100;
}

if (vIsUpperAtToV) {
update(embVs3.values, 0, newLengthV, EMPTY);
update(embVs3.values, newLengthV, newLengthV + newLengthToV, EMPTY);
} else {
update(embVs3.values, 0, newLengthToV, EMPTY);
update(embVs3.values, newLengthToV, newLengthToV + newLengthV, EMPTY);
}

int afterSameLineV = simulateAdds(embVs1.values, 0, embVs1.length, sameLineV);
int afterV;
int afterToV;
if (vIsUpperAtToV) {
afterV = simulateAdds(embVs3.values, 0, newLengthV, v);
afterToV = simulateAdds(embVs3.values, newLengthV, newLengthV + newLengthToV, toV);
} else {
afterToV = simulateAdds(embVs3.values, 0, newLengthToV, toV);
afterV = simulateAdds(embVs3.values, newLengthToV, newLengthToV + newLengthV, v);
}

int newScore = score + beforeV + beforeToV + beforeSameLineV + afterV + afterToV + afterSameLineV;

for (int i = change.length - 1; i >= 0; i--) {
int value = change.values[i];
int embR = (value >>> 20) & ((1 << 10) - 1);
int embC = (value >>> 10) & ((1 << 10) - 1);
int v3 = (value >>> 0) & ((1 << 10) - 1);
inverseEmb[embR][embC] = v3;
}
change.clear();
if (newScore >= score || sa.accept(newScore, score)) {
removeAll(v);
removeAll(sameLineV);
removeAll(toV);

adds(embVs1.values, 0, embVs1.length, sameLineV);
if (vIsUpperAtToV) {
adds(embVs3.values, 0, newLengthV, v);
adds(embVs3.values, newLengthV, newLengthV + newLengthToV, toV);
} else {
adds(embVs3.values, 0, newLengthToV, toV);
adds(embVs3.values, newLengthToV, newLengthToV + newLengthV, v);
}

score = newScore;

saveBest();
}

}

private void changeLength() {
int v = (int) (NV * rng.nextDouble());

boolean isUpper = rng.nextDouble() < 0.5;

int embV0;
{
assert checkOrder(v);
IntArray embVSet = embVSets[v];
embV0 = embVSet.values[isUpper ? 0 : embVSet.length - 1];
int embR0 = toEmbR(embV0);
if (embR0 == 0) {
isUpper = false;
embV0 = embVSet.values[isUpper ? 0 : embVSet.length - 1];
} else if (embR0 == S - 1) {
isUpper = true;
embV0 = embVSet.values[isUpper ? 0 : embVSet.length - 1];
}
}

int sameLineV = EMPTY;
int embR0 = toEmbR(embV0);
int embC0 = toEmbC(embV0);
if (isLowerRightDirection(embR0, embC0)) {
if (isUpper) {
int r1 = embR0 + dr8[1];
int c1 = embC0 + dc8[1];
if (c1 < 0) {
c1 = 0;
} else if (c1 >= S) {
c1 = S - 1;
}
if (isValid(r1, 0, S)) {
assert inverseEmb[r1][c1] != v;
assert inverseEmb[r1][c1] != EMPTY;
sameLineV = inverseEmb[r1][c1];
}
} else {
int r5 = embR0 + dr8[5];
int c5 = embC0 + dc8[5];
if (c5 < 0) {
c5 = 0;
} else if (c5 >= S) {
c5 = S - 1;
}
if (isValid(r5, 0, S)) {
assert inverseEmb[r5][c5] != v;
assert inverseEmb[r5][c5] != EMPTY;
sameLineV = inverseEmb[r5][c5];
}
}
} else {
if (isUpper) {
int r3 = embR0 + dr8[3];
int c3 = embC0 + dc8[3];
if (c3 < 0) {
c3 = 0;
} else if (c3 >= S) {
c3 = S - 1;
}
if (isValid(r3, 0, S)) {
assert inverseEmb[r3][c3] != v;
assert inverseEmb[r3][c3] != EMPTY;
sameLineV = inverseEmb[r3][c3];
}
} else {
int r7 = embR0 + dr8[7];
int c7 = embC0 + dc8[7];
if (c7 < 0) {
c7 = 0;
} else if (c7 >= S) {
c7 = S - 1;
}
if (isValid(r7, 0, S)) {
assert inverseEmb[r7][c7] != v;
assert inverseEmb[r7][c7] != EMPTY;
sameLineV = inverseEmb[r7][c7];
}
}
}

if (sameLineV == EMPTY) {
return;
}

embVs1.clear();
if (isUpper) {
for (int i = 0; i < embVSets[sameLineV].length; i++) {
embVs1.add(embVSets[sameLineV].values[i]);
}
for (int i = 0; i < embVSets[v].length; i++) {
embVs1.add(embVSets[v].values[i]);
}
} else {
for (int i = 0; i < embVSets[v].length; i++) {
embVs1.add(embVSets[v].values[i]);
}
for (int i = 0; i < embVSets[sameLineV].length; i++) {
embVs1.add(embVSets[sameLineV].values[i]);
}
}

int currentLengthV = embVSets[v].length;
int currentLengthV2 = embVSets[sameLineV].length;

int beforeV = -100 * connectedVsEmb[v].length;
int beforeSameLineV = -100 * connectedVsEmb[sameLineV].length;
if (isConnectedEmb[sameLineV][v] >= 0) {
beforeSameLineV += 100;
}

int newLengthV = 1 + (int) ((currentLengthV + currentLengthV2 - 1) * rng.nextDouble());
int newLengthV2 = currentLengthV + currentLengthV2 - newLengthV;
assert newLengthV > 0;
assert newLengthV2 > 0;

int afterV;
int afterSameLineV;
if (isUpper) {
update(embVs1.values, newLengthV2, newLengthV + newLengthV2, EMPTY);
afterSameLineV = simulateAdds(embVs1.values, 0, newLengthV2, sameLineV);
afterV = simulateAdds(embVs1.values, newLengthV2, newLengthV + newLengthV2, v);
} else {
update(embVs1.values, newLengthV, newLengthV + newLengthV2, EMPTY);
afterV = simulateAdds(embVs1.values, 0, newLengthV, v);
afterSameLineV = simulateAdds(embVs1.values, newLengthV, newLengthV + newLengthV2, sameLineV);
}

int newScore = score + beforeV + beforeSameLineV + afterV + afterSameLineV;

for (int i = change.length - 1; i >= 0; i--) {
int value = change.values[i];
int embR = (value >>> 20) & ((1 << 10) - 1);
int embC = (value >>> 10) & ((1 << 10) - 1);
int v3 = (value >>> 0) & ((1 << 10) - 1);
inverseEmb[embR][embC] = v3;
}
change.clear();
if (newScore >= score || sa.accept(newScore, score)) {
removeAll(v);
removeAll(sameLineV);

if (isUpper) {
adds(embVs1.values, 0, newLengthV2, sameLineV);
adds(embVs1.values, newLengthV2, newLengthV + newLengthV2, v);
} else {
adds(embVs1.values, 0, newLengthV, v);
adds(embVs1.values, newLengthV, newLengthV + newLengthV2, sameLineV);
}

score = newScore;
saveBest();
}
}

private boolean checkOrder(int v) {
IntArray embVSet = embVSets[v];
for (int i = 1; i < embVSet.length; i++) {
if (toEmbR(embVSet.values[i - 1]) >= toEmbR(embVSet.values[i])) {
return false;
}
}
return true;
}

private void swap() {
int v0 = (int) (NV * rng.nextDouble());
int embV0 = embVSets[v0].values[(int) (embVSets[v0].length * rng.nextDouble())];
int embR0 = toEmbR(embV0);
int embC0 = toEmbC(embV0);

int embNextR = -1;
int embNextC = -1;
while (!isValid(embNextR, 0, S) || !isValid(embNextC, 0, S) || inverseEmb[embNextR][embNextC] == v0) {
int d = (int) (dr8.length * rng.nextDouble());
embNextR = embR0 + dr8[d];
embNextC = embC0 + dc8[d];
}

int v = inverseEmb[embNextR][embNextC];

int v2 = connectedVs[v0].values[(int) (connectedVs[v0].length * rng.nextDouble())];
for (int k = 0; k < 3; k++) {
if (v2 != v) {
break;
}
v2 = connectedVs[v0].values[(int) (connectedVs[v0].length * rng.nextDouble())];
}
if (v2 == v) {
return;
}

embVs1.clear();
for (int i = 0; i < embVSets[v].length; i++) {
embVs1.add(embVSets[v].values[i]);
}
embVs2.clear();
for (int i = 0; i < embVSets[v2].length; i++) {
embVs2.add(embVSets[v2].values[i]);
}

int beforeV = -100 * connectedVsEmb[v].length;
int beforeV2 = -100 * connectedVsEmb[v2].length;
if (isConnectedEmb[v2][v] >= 0) {
beforeV2 += 100;
}

update(embVs2.values, 0, embVs2.length, EMPTY);
int afterV2 = simulateAdds(embVs1.values, 0, embVs1.length, v2);
int afterV = simulateAdds(embVs2.values, 0, embVs2.length, v);

int newScore = score + beforeV + beforeV2 + afterV + afterV2;

for (int i = change.length - 1; i >= 0; i--) {
int value = change.values[i];
int embR = (value >>> 20) & ((1 << 10) - 1);
int embC = (value >>> 10) & ((1 << 10) - 1);
int v3 = (value >>> 0) & ((1 << 10) - 1);
inverseEmb[embR][embC] = v3;
}
change.clear();
if (newScore >= score || sa.accept(newScore, score)) {
removeAll(v);
removeAll(v2);

adds(embVs1.values, 0, embVs1.length, v2);
adds(embVs2.values, 0, embVs2.length, v);

score = newScore;
saveBest();

}
}

private IntArray[] bestEmbVSets;

private void saveBest() {
if (score > bestScore) {
bestScore = score;
for (int v = 0; v < NV; v++) {
System.arraycopy(embVSets[v].values, 0, bestEmbVSets[v].values, 0, embVSets[v].length);
bestEmbVSets[v].length = embVSets[v].length;
}
}
}

private void loadBest() {
score = bestScore;
for (int v = 0; v < NV; v++) {
System.arraycopy(bestEmbVSets[v].values, 0, embVSets[v].values, 0, bestEmbVSets[v].length);
embVSets[v].length = bestEmbVSets[v].length;
}
}

private String[] makeSolution() {
String[] res = new String[NV];
for (int v = 0; v < NV; v++) {

IntArray embVSet = embVSets[v];

StringBuilder resV = new StringBuilder();
resV.append(embVSet.length);
for (int i = 0; i < embVSet.length; i++) {
int embV = embVSet.values[i];
resV.append(" " + (embV + 1));
}
res[v] = resV.toString();
}
return res;
}

private boolean isValid(int v, int min, int sup) {
return v >= min && v < sup;
}

private int toEmbV(int embR, int embC) {
return embR * S0 + embC;
}

private int toEmbC(int embV) {
return embV % S0;
}

private int toEmbR(int embV) {
return embV / S0;
}

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

String line = br.readLine();
String[] split = line.split(" ");
int NV = Integer.parseInt(split[0]);
int NE = Integer.parseInt(split[1]);

int[] u = new int[NE];
int[] v = new int[NE];
for (int i = 0; i < NE; i++) {
line = br.readLine();
split = line.split(" ");
u[i] = Integer.parseInt(split[0]);
v[i] = Integer.parseInt(split[1]);
}

line = br.readLine();
split = line.split(" ");
int NEmbV = Integer.parseInt(split[0]);
int NEmbE = Integer.parseInt(split[1]);

int[] a = new int[NEmbE];
int[] b = new int[NEmbE];
for (int i = 0; i < NEmbE; i++) {
line = br.readLine();
split = line.split(" ");
a[i] = Integer.parseInt(split[0]);
b[i] = Integer.parseInt(split[1]);
}

Main main = new Main();
String[] ret = main.run(NV, NE, u, v, NEmbV, NEmbE, a, b);
for (int i = 0; i < ret.length; ++i) {
System.out.println(ret[i]);
}
System.out.flush();
} catch (Exception e) {
e.printStackTrace();
}
}

}

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 Edge {
int u;
int v;

public Edge(int u, int v) {
super();
this.u = u;
this.v = v;
}

}

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) {
add(value);
return;
}

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

}

class SAState {

public static final boolean useTime = true;

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

public double startTemperature = 50;
public double endTemperature = 5;
public double temperature = startTemperature;
public double lastAcceptTemperature = startTemperature;

public double startRange = 1 << 20;
public double endRange = 1 << 20;
public double range = startRange;

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

public void init() {
loop = 0;
countChange = 0;
countAccept = 0;
lastAcceptTemperature = startTemperature;
startTime = useTime ? Main.watch.getSecond() : loop;

updateTime();
updateTemperature();
updateRange();
}

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 ? Main.watch.getSecond() : loop;
}

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

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

}