Problem Description

You are given two integers $n,k$. Now you have a graph with $2^n$ vertices, numbered $0\sim 2^n-1$. For any two vertices $x,y$, there is an edge between them if and only if $\mathrm{popc}(x\oplus y)=1$, that is, these two numbers differ in exactly one bit in binary.

You need to choose $k$ simple cycles (cycles with no repeated vertices) in this graph, such that each vertex belongs to exactly one simple cycle. You need to output a construction or report that there is no solution.

Input Format

This problem contains multiple test cases. The first line contains an integer $T$ indicating the number of test cases.

Each test case contains one line with two integers $n,k$.

Output Format

Output separately for each test case.

If you think this test case has no solution, output one line with the string $\texttt{No}$.

Otherwise, first output one line with the string $\texttt{Yes}$, followed by $k$ lines.

In each line, the first integer $l$ denotes the length of the cycle, then output $v_1,v_2,v_3,\dots,v_l$ in the order along the cycle.

You must ensure that these vertices are all distinct, and for $1\le i<l$, there is an edge between $v_i$ and $v_{i+1}$. In particular, there is an edge between $v_l$ and $v_1$.

You must ensure that among the $2^n$ vertices, each vertex belongs to exactly one simple cycle. You must ensure $l\ge 3$.

2
2 1
3 2

Yes
4 0 1 3 2
Yes
4 0 1 3 2
4 4 5 7 6

Hint

Special property A: $k=1$.

For all testdata, $1\le T\le 10$, $1\le n\le 17$, $1\le k \le 2^{n}$.

Translated by ChatGPT 5