P11313 [RMI 2021] 园艺 / Gardening

译自 [9th Romanian Master of Informatics, RMI 2021](https://rmi.lbi.ro/rmi_2021/) D1T1。$\texttt{1s,0.5G}$。

现在要在 $N$ 行 $M$ 列的矩形格子内种花，每个格子内种一株花。一共有 $K$ 种品种的花，编号为 $1\sim K$。 为了让花更好看，以下条件必须满足： - 每种花至少出现一株。 - 每种花所在的格子形成一个四连通块。 - 与格子 $(i,j)$ 四连通的格子中，**恰好**有两个格子种的花与 $(i,j)$ 种的花的品种相同。 请你构造一组方案，或者指出这是不可能实现的。

**本题单个测试点内有多组测试数据。** 第一行，一个正整数 $T$，表示测试数据组数。 接下来 $T$ 组测试数据，每组测试数据包含一行三个正整数 $N,M,K$。

对于每组测试数据： - 如果不可能构造，输出一行一个 $\texttt{NO}$； - 否则，输出一行一个 $\texttt{YES}$；接下来 $N$ 行，每行 $M$ 个正整数，描述一个方案。 任意一组合法方案都可以得分。

对于 $100\%$ 的数据，保证： - $1\le N,M\le 2\times 10^5$； - $1\le K\le N\cdot M$； - $1\le T\le 10^5$； - 令 $S$ 为**有解**的测试数据中的 $\sum N\cdot M$，则 $S\le 2\times 10^5$。 | 子任务编号 | $N\le $ | 特殊性质 | 得分 | | :--: | :--: | :--: | :--: | | $ 1 $ | $ 4 $ | A | $5$ | | $ 2 $ | $ 4 $ | | $6$ | | $ 3 $ | $ 6 $ | | $10$ | | $ 4 $ | $ 2\times 10^5$ | B | $18$ | | $ 5 $ | $ 2\times 10^5$ | C | $39$ | | $ 6 $ | $ 2\times 10^5$ | | $22$ | - 特殊性质 A：$M\le 4$。 - 特殊性质 B：$N=M$。 - 特殊性质 C：$K$ 在 $[1,N\cdot M]$ 中等概率独立随机选取。