Problem Description

Consider a graph $ G=(V,E) $ consisting of a vertex set $ V $ and an edge set $ E $. Given two graphs $ G=(V, E) $ and $ G_{emb}=(V_{emb},E_{emb}) $, where each edge in graph $ G $ is assigned a weight. Under the constraints described in the input and output sections, map each element of $ V $ to a vertex in $ V_{emb} $ such that the score described below is maximized. Note that $ G_{emb} $ is a square-shaped King's Graph where the number of vertices in each row and column is equal. The numbering of vertices in the King's Graph starts at the top-left corner with $ 1 $, and proceeds from left to right, row by row.

Input Format

The input is provided via standard input in the following format. All values are integers.

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

• $ |V| $ and $ |E| $ represent the number of vertices and edges in graph $ G $, respectively.
• $ u_i, v_i, w_i $ provide information about the edges in graph $ G $, indicating that vertex $ u_i $ is connected to vertex $ v_i $ with an edge of weight $ w_i $.
• $ |V_{emb}| $ and $ |E_{emb}| $ represent the number of vertices and edges in graph $ G_{emb} $, respectively.
• $ a_i, b_i $ provide information about the edges in graph $ G_{emb} $, indicating that vertex $ a_i $ is connected to vertex $ b_i $.

Constraints for graph $ G $

• $2 \leq |V| \leq 5 \times 10^2$
• $1 \leq |E| \leq min(|V|(|V|-1)/2, 2 \times 10^4)$
• $1 \leq u_i < v_i \leq |V|$
• $0 \leq w_i \leq 15$
• If $i \neq j$, then $u_i \neq u_j$ or $v_i \neq v_j$
• The given graph is connected

Constraints for 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 perfect square
• $|V| \leq |V_{emb}|$
• $1 \leq a_i < b_i \leq |V_{emb}|$

Output Format

Output should be provided in the following format to standard output over $ |V| $ lines.

$ s_1 $ $ t_1 $ $ s_2 $ $ t_2 $ : $ s_{|V|} $ $ t_{|V|} $

• $ s_i, t_i $ indicate that vertex $ s_i $ in graph $ G $ corresponds to vertex $ t_i $ in graph $ G_{emb} $.
• All vertices in graph $ G $ must have a clear correspondence to vertices in graph $ G_{emb} $, and each vertex in $ G_{emb} $ must correspond uniquely to a vertex in $ G $. See the output constraints for details.

Output Constraints

• The output consists of $ |V| $ lines.
• $1 \leq s_i \leq |V|$
• $1 \leq t_i \leq |V_{emb}|$
• If $i \neq j$, then $s_i \neq s_j$ and $t_i \neq t_j$

Sample Input and Output

Sample Input #1

3 3
1 2 1
2 3 2
1 3 4
9 20
1 2
1 4
1 5
2 4
2 3
2 5
2 6
3 5
4 5
4 7
4 8
5 7
5 6
5 8
5 9
6 8
3 6
6 9
7 8
8 9

Sample Output #1

1 1
2 2
3 5

Sample Input #2

7 21
1 2 8
1 3 14
1 4 7
1 5 14
1 6 15
1 7 7
2 3 7
2 4 0
2 5 13
2 6 14
2 7 13
3 4 12
3 5 1
3 6 8
3 7 8
4 5 8
4 6 3
4 7 8
5 6 9
5 7 9
6 7 1
64 210
1 2
1 9
1 10
2 9
2 3
2 10
2 11
3 10
3 4
3 11
3 12
4 11
4 5
4 12
4 13
5 12
5 6
5 13
5 14
6 13
6 7
6 14
6 15
7 14
7 8
7 15
7 16
8 15
9 10
9 17
9 18
10 17
10 11
10 18
10 19
11 18
11 12
11 19
11 20
12 19
12 13
12 20
12 21
13 20
13 14
13 21
13 22
14 21
14 15
14 22
14 23
15 22
15 16
15 23
15 24
16 23
17 18
17 25
17 26
18 25
18 19
18 26
18 27
19 26
19 20
19 27
19 28
20 27
20 21
20 28
20 29
21 28
21 22
21 29
21 30
22 29
22 23
22 30
22 31
23 30
23 24
23 31
23 32
24 31
25 26
25 33
25 34
26 33
26 27
26 34
26 35
27 34
27 28
27 35
27 36
28 35
28 29
28 36
28 37
29 36
29 30
29 37
29 38
30 37
30 31
30 38
30 39
31 38
31 32
31 39
31 40
32 39
33 34
33 41
33 42
34 41
34 35
34 42
34 43
35 42
35 36
35 43
35 44
36 43
36 37
36 44
36 45
37 44
37 38
37 45
37 46
38 45
38 39
38 46
38 47
39 46
39 40
39 47
39 48
40 47
41 42
41 49
41 50
42 49
42 43
42 50
42 51
43 50
43 44
43 51
43 52
44 51
44 45
44 52
44 53
45 52
45 46
45 53
45 54
46 53
46 47
46 54
46 55
47 54
47 48
47 55
47 56
48 55
49 50
49 57
49 58
50 57
50 51
50 58
50 59
51 58
51 52
51 59
51 60
52 59
52 53
52 60
52 61
53 60
53 54
53 61
53 62
54 61
54 55
54 62
54 63
55 62
55 56
55 63
55 64
56 63
8 16
16 24
24 32
32 40
40 48
48 56
56 64
57 58
58 59
59 60
60 61
61 62
62 63
63 64

Sample Output #2

1 10
2 9
3 17
4 11
5 2
6 1
7 18

Notes/Hints

Scoring

The score for each test case and the total score for this problem are calculated as follows:

• For each edge $ (u, v) $ in $ G $, add its weight to the score if there is an edge $ (p, q) $ in $ G_{emb} $, where $ p $ is the vertex in $ G_{emb} $ corresponding to $ u $ and $ q $ is the vertex in $ G_{emb} $ corresponding to $ v $.
• The score for a test case is the sum of the weights of edges in $ G $ that satisfy the above condition.
• There are 30 test cases in total (18 random graphs and 12 complete graphs), and the total score for this problem is the sum of the scores for each test case.
• Test cases that exceed the time or memory limits or do not follow the correct output format will receive 0 points.

Note: The final ranking and scores will be determined by a system test conducted after the contest. This test will rejudge the final submissions using 150 different judge data sets, generated in the same way as the test cases but with different seeds. The system test is designed to prevent high scores through tuning based on specific seeds, and the final ranking will be determined by this test.

Graph Generation

For all test cases, the given graph $ G $ is either a "random graph" or a "complete graph". The generation methods for each type are briefly described below. For more details, refer to the sample code.

Random Graph

• Initially, a tree with $ |V| $ vertices is generated randomly, and then $ |E| - |V| + 1 $ edges are added randomly, with each edge in the graph assigned a random weight.
• Among the random graphs, 8 cases have a maximum degree of 8 for each vertex, generated by avoiding adding edges to vertices already having a degree of 8.

Complete Graph

• For all pairs $ (u, v) $ where $1 \leq u < v \leq |V|$, an edge is created with a random weight $ w $.

Generator and Tester, and References

The generator and tester for this problem can be downloaded from here.

The following literature may be helpful in solving this problem. You may refer to it while creating your solution.

H. Neven, et al., "NIPS 2009 demonstration: Binary classification using hardware implementation of quantum annealing." Quantum (2009): 1-17.

Sample Explanation 2

The illustration for this input example is as follows:

见题面 Input 部分

见题面 Output 部分