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
1. Choose a positive integer **K**
2. 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)
3. 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:
1. **Complete Coverage**: For each j (1 ≤ j ≤ N), there is at least one cell with color j
2. **Adjacency Preservation**: For each pair of adjacent countries (A[i], B[i]), there is at least one pair of adjacent cells where one is colored A[i] and the other is colored B[i]
- Two cells are adjacent if they share a side
3. **No False Adjacencies**: For each pair of adjacent cells with different colors, the countries represented by these two colors were adjacent during the Tiwanaku Period
### Example
If **N = 3**, **M = 2** and the pairs of adjacent countries are **(1,2)** and **(2,3)**, then the pair **(1,3)** was not adjacent.
The following map of dimension **K = 3** satisfies all conditions:
```
2 3 3
2 3 2
1 2 1
```
**Note:** A country does not need to form a connected region on the map. In the map above, country 3 forms a connected region, while countries 1 and 2 form disconnected regions.
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 the value of K**, and lower values of K may result in a better score. However, finding the minimum possible value of K is not required.
Implementation Details
--------------------------------------------------
You should implement the following procedure:
```cpp
std::vector<std::vector<int>> create_map(int N, int M,
std::vector<int> A, std::vector<int> B)
```
### Parameters
- **N**: The number of countries
- **M**: The number of pairs of adjacent countries
- **A** and **B**: Arrays of length M describing adjacent countries
### Return Value
The procedure should return an array **C** that represents the map:
- Let K be the length of C
- Each element of C must be an array of length K
- Values must be integers between 1 and N inclusive
- C[i][j] is the color of the cell at row i and column j (for 0 ≤ i, j < K)
- **K must be less than or equal to 240**
Constraints
--------------------------------------------------
- 1 ≤ N ≤ 40
- 0 ≤ M ≤ N·(N−1)/2
- 1 ≤ A[i] < B[i] ≤ N for each i such that 0 ≤ i < M
- The pairs (A[0], B[0]), ..., (A[M−1], B[M−1]) are distinct
- There exists at least one map which satisfies all the conditions
Scoring
--------------------------------------------------
You need to make **R = K/N** as small as possible. A smaller R will result in a better score.
Examples
--------------------------------------------------
### Example 1
**Call:**
```cpp
create_map(3, 2, [1, 2], [2, 3])
```
This is the example from the task description. The procedure can return:
```cpp
[
[2, 3, 3],
[2, 3, 2],
[1, 2, 1]
]
```
### Example 2
**Call:**
```cpp
create_map(4, 4, [1, 1, 2, 3], [2, 3, 4, 4])
```
In this example:
- **N = 4**, **M = 4**
- Adjacent country pairs: (1,2), (1,3), (2,4), (3,4)
- Not adjacent: (1,4), (2,3)
The procedure can return the following map of dimension **K = 7**:
```cpp
[
[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]
]
```
The map could be smaller. For example, the following map of dimension **K = 2**:
```cpp
[
[3, 1],
[4, 2]
]
```
**Note:** Both maps satisfy K/N ≤ 2.
Sample Grader
--------------------------------------------------
### Input Format
```
T # Number of scenarios
N M # First scenario
A[0] B[0]
...
A[M-1] B[M-1]
```
### Output Format
```
P # Length of array C
Q[0] Q[1] ... Q[P-1] # Length of each row
C[0][0] ... C[0][Q[0]-1] # First row
...
C[P-1][0] ... C[P-1][Q[P-1]-1] # Last row
```
Here, P is the length of the array C returned by `create_map`, and Q[i] (0 ≤ i < P) is the length of C[i].