Problem

In what follows assume we are given two graphs. The first graph $G=(V, E)$ consists of a set of vertices $V$ and edges $E$. The second graph $G_{emb} = (V_{emb}, E_{emb})$ also consists of a set of vertices $V_{emb}$ and edges $E_{emb}$ and shall be a square King's Graph, with vertices labeled from left to right and top to bottom, as illustrated in the figure below. The task is to find a map $s$ which assigns each vertex $i\\in V$ to a subset of vertices $s(i) ⊂ V_{emb}$ such that:

• For any vertex $i \\in V$ the subgraph induced by $s(i)$ in $G_{emb}$ is connected;
• The subsets $s(i), s(j) ⊂ V_{emb}$ are mutually exclusive, i.e., for any $i,j \\in V$ with $i\\neq j$ we have $s(i)∩ s(j)=Ø$;
• For any vertex $i \\in V$ the subset $s(i)$ must not be empty.

Score

For each run of your algorithm on a single input graph, the score obtained by the resulting map $s$ is evaluated as follows:

• An initial score of $5000$ points is assigned.
• We add $100$ points to the initial score for each edge $(i,j) \\in E$, if the corresponding vertex sets $s(i), s(j) ⊂ V_{emb}$ are connected by at least one edge of the King's graph $G_{emb}$.
• We add a bonus of $100000$ points, if the algorithm finds a map $s$ such that for every edge $(i,j)\\in E$, the corresponding vertex sets $s(i), s(j) ⊂ V_{emb}$ are connected by at least one edge of the King's graph $G_{emb}$. Note that finding a map $s$ which obtains the bonus score may not be possible on every input graph.
• Large clusters are penalized by subtracting $∑ _{u \\in V} (|s(u)|-1)$ points from the score.
• The score becomes $0$ in any of the following cases:

1. If the subgraph induced by any of the vertex sets $s(i)$ in $G_{emb}$ is disconnected. See Example 1 in the figure below.
2. If the vertex sets of $s(i), s(j)$ are not mutually exclusive, i.e., if any of the vertex sets with $(i \\neq j)$ overlap on some element. See Example 2 in the figure below.
3. If the subset $s(i)$ is empty, i.e., $|s(i)| = 0$.
4. Furthermore, any run of your algorithm which exceeds either the time or the memory limit will not contribute to your final score. The same is true for any output, which violates the output format specified below.

Two example assignments for which the final score is $0$. Example1: The subgraph induced by the upper vertex set (as marked by red rectangles) is disconnected. Example 2: The vertex sets (as marked by a blue and a magenta rectangle) overlap.

• For the period of the contest we will evaluate your score, by running your algorithm on 30 input graphs $G$ and adding up the corresponding score. This will allow for a preliminary estimate of your rank.
• After the contest has finished your final score and rankings will be determined by running your final submission on $150$ previously undisclosed input graphs.

---

Input

Inputs are given in the following format through the standard input. All the inputs have integer values.

$|V|$ $|E|$ $u_1$ $v_1$ $u_2$ $v_2$ : $u_{|E|}$ $v_{|E|}$ $|V_{emb}|$ $|E_{emb}|$ $a_1$ $b_1$ $a_2$ $b_2$ : $a_{|E_{emb}|}$ $b_{|E_{emb}|}$

• $|V|$ and $|E|$ denote the total number of vertices and edges of the graph $G$, respectively.
• The line $u_i, v_i$ means that the vertex $u_i$ and the vertex $v_i$ of the graph $G$ are connected.
• $|V_{emb}|$ and $|E_{emb}|$ denote the total number of vertices and edges of the graph $G_{emb}$, respectively.
• The line $a_i, b_i$ means that the vertex $a_i$ and the vertex $b_i$ of the graph $G_{emb}$ are connected by an edge.

Constraints on the Graph $G$

• $2 \\leq |V| \\leq 5 \\times 10^2$
• $1 \\leq |E| \\leq min ( \\frac{|V| \\times (|V|-1)}{2}, 2 \\times 10^4 )$
• $1 \\leq u_i \\lt v_i \\leq |V|$
• For any pair $i \\neq j$, we have that either $u_i \\neq u_j$ or $v_i \\neq v_j$.
• The graph $G$ is connected.

Constraints on the Graph $G_{emb}$

• $G_{emb}$ is a square King's graph.
• $4 \\leq |V_{emb}| \\leq 3.6 \\times 10^3$ and $|V_{emb}|$ is a square number.
• $|V| \\leq |V_{emb}|$
• $1 \\leq a_i \\lt b_i \\leq |V_{emb}|$

Output

Output should be in the following format consisting of $|V|$ lines and should be processed through the standard output.

$n_1$ $x_{1,1}$ $x_{1,2}$ ... $x_{1,n_1}$ $n_2$ $x_{2,1}$ $x_{2,2}$ ... $x_{2,n_2}$ : $n_{|V|}$ $x_{|V|,1}$ $x_{|V|,2}$ ... $x_{|V|,n_{|V|}}$

• The index $i$ in $n_{i}$ denotes the $i$-th vertex of graph $G$.
• $n_{i}$ denotes the total number of vertices in $s(i)⊂ V_{emb}$, assigned to the $i$-th vertex of graph $G$.
• $x_{i,j}$ denotes the $j$-th element of subset $s(i)$, which is assigned to the $i$-th vertex of graph $G$.

Constraints for the Output

• Output should consist of $|V|$ lines.
• $1 \\leq n_i$
• $1 \\leq x_{i,j} \\leq |V_{emb}|$
• $i \\neq j$ or $k \\neq l$ implies that $x_{i,k} \\neq x_{j,l}$

How are the Input Graphs $G$ Generated

For evaluating your final score, we will run your algorithm on random input graphs $G$. These graphs are generated as follows: First, a tree with $|V|$ vertices is generated randomly. Subsequently, $|E| − |V| + 1$ edges are randomly added to the tree. For details see the sample code.

---

Input Example 1

7 14
1 2
1 3
1 6
1 7
2 4
2 5
2 6
2 7
3 5
3 7
4 5
4 6
4 7
5 7
25 72
1 2
1 6
1 7
2 6
2 3
2 7
2 8
3 7
3 4
3 8
3 9
4 8
4 5
4 9
4 10
5 9
6 7
6 11
6 12
7 11
7 8
7 12
7 13
8 12
8 9
8 13
8 14
9 13
9 10
9 14
9 15
10 14
11 12
11 16
11 17
12 16
12 13
12 17
12 18
13 17
13 14
13 18
13 19
14 18
14 15
14 19
14 20
15 19
16 17
16 21
16 22
17 21
17 18
17 22
17 23
18 22
18 19
18 23
18 24
19 23
19 20
19 24
19 25
20 24
5 10
10 15
15 20
20 25
21 22
22 23
23 24
24 25

Output Example 1

3 14 15 20
1 19
1 9
1 23
1 18
1 25
1 13

The input example 1 from above is visualized in the figure below. The left side shows the input graph with 7 vertices, labeled by indices $V1$ to $V7$. The right side shows a King graph of size $5\\times5$. The map $s$ as specified by the output of example 1 is visualized by colored boxes. For example, the vertex $V1$ of the input graph is mapped to a set of three vertices on the kings graph.

We now discuss the score assigned to the map $s$ as specified by output example 1:

• The initial score is $5000$ points.
• We add $11 \\times 100 = 1100$ points to the initial score, i.e., 100 points for every edge of the input graph, if the corresponding vertex sets are connected by at least one edge of the King's graph. To this end consider for example the edge between the vertex pair $(V1, V2)$. Clearly, the corresponding vertex sets on the King's graph are connected. Therefore, we add 100 points for this edge. On the other hand, consider the vertex pair $(V3, V5)$. The corresponding vertex sets on the King's graph are not connected. Therefore, this edge does not contribute to the score and we mark it by a red cross. Repeating this procedure for every edge of the input graph, we find that $11$ edges of this example score, while $3$ edges (as marked by a red cross) do not score.
• The bonus points of output example 1 are $0$ because the vertex sets corresponding to some edges of the input graph (as marked by a red cross), are not connected by a direct edge of the King's graph.
• We subtract $(3-1) + (1-1) + (1-1) + (1-1) + (1-1) + (1-1) + (1-1)= 2$ points, where the first number in each bracket corresponds to the number of elements in each vertex set on the right. Altogether we lose 2 points because the vertex set $s(V1)$ contains three elements.
• Altogether output example 1 scores because the vertex sets $s(i)$ are mutually exclusive and each vertex set $s(i)$ induces a connected subgraph of the King's graph.

Input Example 2

10 30
3 10
3 6
5 10
5 8
2 6
2 7
1 5
1 9
4 10
5 7
4 6
2 8
1 2
7 10
2 4
1 3
7 8
1 8
6 9
2 9
1 4
2 10
2 3
6 10
8 10
6 8
5 6
3 8
7 9
4 9
16 42
1 2
1 5
1 6
2 5
2 3
2 6
2 7
3 6
3 4
3 7
3 8
4 7
5 6
5 9
5 10
6 9
6 7
6 10
6 11
7 10
7 8
7 11
7 12
8 11
9 10
9 13
9 14
10 13
10 11
10 14
10 15
11 14
11 12
11 15
11 16
12 15
4 8
8 12
12 16
13 14
14 15
15 16

Output Example 2

1 5
2 7 10
1 1
1 2
1 12
1 6
1 15
1 9
1 4
4 3 8 11 14

The input example 2 corresponds to the following schematic figure.

Sample Code and References

• Sample code including source code for generating random input graphs and evaluating the corresponding score of your algorithm can be downloaded through the following link.
• For a previous study of the graph embedding problem, see:

J. Cai, et al., "A practical heuristic for finding graph minors", arXiv:1406.2741 [quant-ph]