FrontierCS

Mr. Pacha, a Bolivian archeologist, discovered an ancient document near Tiwanaku that describes the world during the Tiwanaku Period (300–1000 CE). At that time, there were N countries, numbered from 1 to N.

The document contains a list of M different pairs of adjacent countries:

(A[0], B[0]), (A[1], B[1]), ..., (A[M-1], B[M-1])

For each i (0 ≤ i < M), the document states that country A[i] was adjacent to country B[i] and vice versa. Pairs of countries not listed were not adjacent.

Task

Mr. Pacha wants to create a map of the world such that all adjacencies between countries are exactly as they were during the Tiwanaku Period.

Map Creation Process

Choose a positive integer K
Draw the map as a grid of K × K square cells
- Rows numbered from 0 to K−1 (top to bottom)
- Columns numbered from 0 to K−1 (left to right)
Color each cell using one of N colors (colors numbered 1 to N)
- Country j (1 ≤ j ≤ N) is represented by color j

Coloring Constraints

The coloring must satisfy all of the following conditions:

Complete Coverage: For each j (1 ≤ j ≤ N), there is at least one cell with color j
Adjacency Preservation: For each pair of adjacent countries (A[i], B[i]), there must be at least one pair of adjacent cells (sharing a side) colored A[i] and B[i].
No False Adjacencies: Any two adjacent cells with different colors must correspond to countries that were adjacent during the Tiwanaku Period.

Example

If N = 3, M = 2, and the adjacent country pairs are (1,2) and (2,3), then the pair (1,3) was not adjacent.

A valid map with K = 3:


2 3 3
2 3 2
1 2 1

Note: A country does not need to form a connected region.

Your Task

Help Mr. Pacha choose a value of K and create a map. The document guarantees that such a map exists.

Since Mr. Pacha prefers smaller maps, your score depends on K, but finding the minimum possible K is not required.

Implementation Details

You should implement:

std::vector<std::vector<int>> create_map(
    int N, int M,
    std::vector<int> A, std::vector<int> B
);

Parameters

N: number of countries
M: number of adjacency pairs
A, B: arrays of length M describing the adjacencies

Return Value

Return a matrix C:

Let K be the length of C
Each C[i] must be an array of length K
Values must lie between 1 and N
C[i][j] is the color
K ≤ 240

Constraints

1 ≤ N ≤ 40
0 ≤ M ≤ N·(N−1)/2
1 ≤ A[i] < B[i] ≤ N
All (A[i], B[i]) are distinct
A valid map exists

Scoring

You want R = K / N to be as small as possible.

Examples

Example 1

Call:

create_map(3, 2, [1, 2], [2, 3]);

Possible output:

[
  [2, 3, 3],
  [2, 3, 2],
  [1, 2, 1]
]

Example 2

Call:

create_map(4, 4, [1, 1, 2, 3], [2, 3, 4, 4]);

Adjacency:

Adjacent: (1,2), (1,3), (2,4), (3,4)
Not adjacent: (1,4), (2,3)

Valid K = 7 map:

[
  [2, 1, 3, 3, 4, 3, 4],
  [2, 1, 3, 3, 3, 3, 3],
  [2, 1, 1, 1, 3, 4, 4],
  [2, 2, 2, 1, 3, 4, 3],
  [1, 1, 1, 2, 4, 4, 4],
  [2, 2, 1, 2, 2, 4, 3],
  [2, 2, 1, 2, 2, 4, 4]
]

A smaller K = 2 map also works:

[
  [3, 1],
  [4, 2]
]

Sample Grader

Input Format

T
N M
A[0] B[0]
...
A[M-1] B[M-1]

Output Format

P
Q[0] Q[1] ... Q[P-1]
C[0][0] ... C[0][Q[0]-1]
...
C[P-1][0] ... C[P-1][Q[P-1]-1]

P is the number of rows, and Q[i] is the length of row i.

Problem Metadata

Competition: IOI 2024 — Day 1 Language: English (ISC)

Model Information

Model: GPT 5 Thinking Score: 46.0

Solution Code

#include <bits/stdc++.h>
using namespace std;

// (code unchanged)
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    ...
}

int main() {
    ...
}

World Map

Instruction