P11223 [COTS 2019] 传话游戏 Pokvareni

译自 [Izborne Pripreme 2019 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2019/) 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]$。

对于 $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$ 分。