Clique Partition
Description
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.
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$).
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.
Input
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
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.
描述
给定两个整数和。有一个包含个顶点的图，顶点从到编号，最初没有边。
你需要为每个顶点分配一个整数；设表示顶点上的整数。所有的应该是从到的不同整数。
在分配整数之后，对于每一对顶点，如果，则在它们之间添加一条边。
你的目标是创建一个图，该图可以被分割成可能的（对于给定的和值）最少数量的团。图中的每个顶点应该属于且只属于一个团。回顾一下，一个团是一个顶点集，其中每一对顶点都互相通过边相连。
由于BledDest并没有真正提升他的编程技能，他无法解决问题“给定一个图，将其划分为最少数量的团”。因此，我们还要求你打印出具体的划分方案。
输入
第一行包含一个整数（），表示测试用例的数量。
每个测试用例包含一行，包含两个整数和（；）。
输出
对于每个测试用例，打印三行：
- 第一行应包含个不同的整数（），表示你分配给顶点的值；
- 第二行应包含一个整数（），表示你将图划分为的团的数量；
- 第三行应包含个整数（），表示图的划分方式。如果两个顶点和在同一个团中，则。
如果存在多个答案，则输出其中任意一个。
3
2 3
5 4
8 16
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