Clique Partition
Contest: Educational Codeforces Round 163 (Rated for Div. 2)
Difficulty rating: 2100
Tags: brute force, constructive algorithms, graphs, greedy, implementation

You are given two integers, $$$n$$$ and $$$k$$$. There is a graph on $$$n$$$ vertices, numbered from $$$1$$$ to $$$n$$$, which initially has no edges.

You have to assign each vertex an integer; let $$$a_i$$$ be the integer on the vertex $$$i$$$. All $$$a_i$$$ should be distinct integers from $$$1$$$ to $$$n$$$.

After assigning integers, for every pair of vertices $$$(i, j)$$$, you add an edge between them if $$$|i - j| + |a_i - a_j| \le k$$$.

Your goal is to create a graph which can be partitioned into the minimum possible (for the given values of $$$n$$$ and $$$k$$$) number of cliques. Each vertex of the graph should belong to exactly one clique. Recall that a clique is a set of vertices such that every pair of vertices in it are connected with an edge.

Since BledDest hasn't really brushed his programming skills up, he can't solve the problem "given a graph, partition it into the minimum number of cliques". So we also ask you to print the partition itself.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 1600$$$) — the number of test cases.

Each test case consists of one line containing two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 40$$$; $$$1 \le k \le 2n$$$).

Output format:
For each test case, print three lines:

- the first line should contain $$$n$$$ distinct integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the values you assign to the vertices;
- the second line should contain one integer $$$q$$$ ($$$1 \le q \le n$$$) — the number of cliques you partition the graph into;
- the third line should contain $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le q$$$) — the partition of the graph into cliques. Where two vertices $$$u$$$ and $$$v$$$ are in the same clique if $$$c_u = c_v$$$.

If there are multiple answers, print any of them.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
3
2 3
5 4
8 16

Example output:
2 1
1
1 1
3 1 5 2 4
2
1 1 2 1 2
1 2 3 4 5 6 7 8
1
1 1 1 1 1 1 1 1

Editorial:
There are two main steps to solve the problem:
• analyzing the maximum size of a clique;
• showing a construction that always allows us to get a clique of the maximum possible size.
Firstly, the maximum size of a clique cannot exceed $$$k$$$. If there are at least $$$k+1$$$ vertices in the same clique, then at least two of them (call them $$$i$$$ and $$$j$$$) have $$$|i - j| \ge k$$$. And since $$$a_i \ne a_j$$$, then $$$|a_i - a_j| \ge 1$$$. So, $$$|i - j| + |a_i - a_j|$$$ is at least $$$k+1$$$, so these two vertices won't have an edge connecting them (and cannot belong to the same clique).
Secondly, let's try to find a construction that always allows us to get cliques of size $$$k$$$. To do this, try to solve the problem when $$$k = n$$$; and if $$$n > k$$$, we can split all vertices into $$$\lceil \frac{n}{k} \rceil$$$ cliques as follows: for each clique, we assign a consecutive block of vertices and numbers that will be assigned to them (for example, vertices from $$$1$$$ to $$$k$$$ and numbers from $$$1$$$ to $$$k$$$ belong to the first clique, vertices from $$$k+1$$$ to $$$2k$$$ and numbers from $$$k+1$$$ to $$$2k$$$n belong to the second clique), and then use the solution for $$$n = k$$$ on each of these blocks.
To obtain a solution for $$$n = k$$$, you can either try bruteforcing it locally on, say, $$$n \le 10$$$ and analyzing the results. One of the possible constructions is as follows: let $$$m = \lceil \frac{k}{2} \rceil$$$; split all vertices and numbers from $$$1$$$ to $$$k$$$ into two blocks: $$$[1, m]$$$ and $$$[m + 1, k]$$$; and then, in each block, the greater the index of the vertex, the less the integer it gets. So it looks as follows: $$$a_1 = m, a_2 = m-1, \dots, a_m = 1, a_{m+1} = n, a_{m+2} = n-1, \dots, a_n = m+1$$$. We can show that the "distance" between any two vertices in different halves is exactly $$$k$$$, and the distance between any two vertices in the same half is at most $$$2(m-1)$$$, which never exceeds $$$k$$$.