题目背景

译自 Izborne Pripreme 2019 (Croatian IOI/CEOI Team Selection) D1T3。$\texttt{1s,0.5G}$。

题目描述

提示：搬题人在题面的最后提供了简要题意。

老师带着 $N$ 个小朋友玩传话游戏。他们都知道同样的 $M$ 个单词，我们不妨编号为 $1\sim M$。

游戏进行方式是这样的：

• 小朋友们被排成一列；
• 老师对第一个小朋友耳语单词 $1$；
• 对于 $1\le i\lt N$，第 $i$ 个小朋友对第 $(i+1)$ 个小朋友耳语听到的词；
• 第 $N$ 个小朋友大声说出他听到的词。

由于当时旁边有 OIer 在大力敲打键盘，游戏受到了干扰，小朋友常常听错词。但是，神奇的是，对于第 $i$ 个小朋友，无论谁对他耳语，以及他在队列中的哪个位置，对他耳语相同的词 $A$，他都会听到相同的词 $B$（$A=B$ 是可能的）。

老师重复进行了 $N!$ 局游戏，每种排列都试了一次。她注意到，有一个词恰好被大声说出 $K$ 次。老师很好奇，于是找来了你，来复现这样的情况。

具体地说，给定整数 $N,K$。构造正整数 $M,X$，以及一种小朋友误听单词的方式，使得在 $N!$ 局游戏中，$X$ 恰好被大声说出 $K$ 次。

找到的 $M$ 越小，得分越高，详见【计分方式】。

简单地说：给定 $N,K$。构造 $N$ 个 $[1,M]\to [1,M]$ 的函数 $f_1(x),f_2(x),\ldots,f_{N}(x)$（$M$ 是你选定的正整数），使得：

• 令 $p_1,p_2,\ldots,p_N$ 取遍 $N!$ 个 $1\sim N$ 的排列；
  • 将 $N!$ 种排列 $p$ 中，$f_{p_N}(f_{p_{N-1}}\cdots(f_{p_2}(f_{p_1}(1)))\cdots)$ 取到的值放入多重集 $S$。则存在 $X\in S$，使得 $X$ 恰好在 $S$ 中出现 $K$ 次。

这里，$[1,M]$ 指的是 $[1,M]\cap \mathbb{Z}$。

目标是使 $M$ 尽量小。

输入格式

本题单个测试点内含有多组测试数据。

第一行，正整数 $\mathrm{id}$，表示子任务编号；

第二行，正整数 $T$，表示测试数据组数；

接下来 $T$ 行，每行两个整数 $N,K$，描述一组数据。

输出格式

对于每组数据，输出 $(N+1)$ 行：

第一行，两个正整数 $M,X$。你需要保证 $1\le X\le M\le 10^4$。

接下来 $N$ 行，每行 $M$ 个正整数。

第 $i$ 行第 $j$ 个正整数 $f_{i}(j)$ 表示：如果对第 $i$ 个小朋友耳语 $j$，他会听到 $f_{i}(j)$。你需要保证 $f_i(j)\in [1,M]$。

1
2
3 2
2 1

3 3
2 1 3
3 2 2
1 3 2
2 1
1 1
2 2

2
2
3 3
4 0

6 2
1 2 3 4 5 6
6 5 4 3 2 1
2 4 1 4 3 2
2 2
1 1
1 1
1 1
1 1

提示

对于 $100\%$ 的数据，保证：

• $\mathrm{id}\in \{1,2\}$；
• $1\le N\le 12$；
• $0\le K\le N!$；
• $1\le T\le 10$。

【计分方式】

本题分为两个子任务计分。

• Subtask $1$（$30$ pts）：保证 $1\le N\le 7$。

  只要构造方案合法，就能获得满分。否则得 $0$ 分。

• Subtask $2$（$70$ pts）：保证 $1\le N\le 12$。

  如果输出不合法，得 $0$ 分。

  否则单组测试数据得分为 $70\cdot k$，$k$ 按照下式计算：

  $$k= \begin{cases} \displaystyle 1, & M\le N+1 \\ \displaystyle 0.7 + \frac{0.15}{M-N-1}\, \in [0.7,0.85], & N+1\lt M\le N+5 \\ \displaystyle 0.5 + 0.05 \left(5-\frac{M}{N}\right) \, \in[0.5,0.7], & N+5\lt M\le 5\cdot N \\ \displaystyle \frac{0.5}{\log_{10}(M/5N)+1}\, \in [0,0.5]& 5\cdot N\lt M\le 10^4 \\ \end{cases}$$

  单个测试点得分是所有测试数据中得分的最小值。例如，样例 $2$ 的两组数据的 $k$ 分别为 $0.77,1$。该输出得 $0.7\cdot 70$ 分。