311194: CF1948E. Clique Partition

E. Clique Partitiontime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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

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.

ExampleInput

3
2 3
5 4
8 16

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

题目大意：
E. Clique Partition（团划分）

给定两个整数n和k。有一个包含n个顶点（编号从1到n）的图，最初没有边。

你必须给每个顶点分配一个整数；设a_i为顶点i上的整数。所有a_i应该是从1到n的不同整数。

在分配整数后，对于每对顶点(i, j)，如果|i - j| + |a_i - a_j| ≤ k，则在它们之间添加一条边。

你的目标是创建一个可以划分为最小可能数目的团的图（对于给定的n和k值）。图中的每个顶点应该恰好属于一个团。回想一下，团是顶点的一个集合，使得其中每对顶点都通过边相连。

由于BledDest的编程技能不强，他无法解决“给定一个图，将其划分为最小数量的团”的问题。所以我们还要求你打印出划分本身。

输入数据格式：
第一行包含一个整数t（1 ≤ t ≤ 1600）——测试用例的数量。
每个测试用例由一行组成，包含两个整数n和k（2 ≤ n ≤ 40；1 ≤ k ≤ 2n）。

输出数据格式：
对于每个测试用例，打印三行：
- 第一行应包含n个不同的整数a_1, a_2, …, a_n（1 ≤ a_i ≤ n）——你分配给顶点的值；
- 第二行应包含一个整数q（1 ≤ q ≤ n）——你将图划分为的团的数量；
- 第三行应包含n个整数c_1, c_2, …, c_n（1 ≤ c_i ≤ q）——图的团划分。如果两个顶点u和v在同一个团中，则c_u = c_v。

如果有多个答案，请打印其中任何一个。题目大意： E. Clique Partition（团划分） 给定两个整数n和k。有一个包含n个顶点（编号从1到n）的图，最初没有边。 你必须给每个顶点分配一个整数；设a_i为顶点i上的整数。所有a_i应该是从1到n的不同整数。 在分配整数后，对于每对顶点(i, j)，如果|i - j| + |a_i - a_j| ≤ k，则在它们之间添加一条边。 你的目标是创建一个可以划分为最小可能数目的团的图（对于给定的n和k值）。图中的每个顶点应该恰好属于一个团。回想一下，团是顶点的一个集合，使得其中每对顶点都通过边相连。 由于BledDest的编程技能不强，他无法解决“给定一个图，将其划分为最小数量的团”的问题。所以我们还要求你打印出划分本身。 输入数据格式： 第一行包含一个整数t（1 ≤ t ≤ 1600）——测试用例的数量。 每个测试用例由一行组成，包含两个整数n和k（2 ≤ n ≤ 40；1 ≤ k ≤ 2n）。 输出数据格式： 对于每个测试用例，打印三行： - 第一行应包含n个不同的整数a_1, a_2, …, a_n（1 ≤ a_i ≤ n）——你分配给顶点的值； - 第二行应包含一个整数q（1 ≤ q ≤ n）——你将图划分为的团的数量； - 第三行应包含n个整数c_1, c_2, …, c_n（1 ≤ c_i ≤ q）——图的团划分。如果两个顶点u和v在同一个团中，则c_u = c_v。 如果有多个答案，请打印其中任何一个。