#HDR003B. 「MCOI-06」Gerrymandering

「MCOI-06」Gerrymandering

题目描述

给定正整数 n,m,kn,m,k,能否将一个 n×mn\times m 表格染色,使得每一个颜色形成恰好一个联通块,并且每一个联通块大小为 kk

如果存在,请构造一个合法方案。

输入格式

本题有多组数据。

第一行一个正整数 TT,表示表示数据的组数。

接下来 TT 行,每行两个正整数 n,m,kn,m,k

输出格式

输出 TT 行,第 ii 行含第 ii 组数据的答案。如果存在,输出 YES,否则,输出 NO

如果存在,接下来输出 nn 行,其中每行 mm 个正整数,其中每一个正整数小于等于 10910^9 并且形成一个大小恰好为 kk 的连通块。

3
3 3 3
3 3 33
6 6 4
YES
1 1 2
1 2 2
3 3 3
NO
YES
1 1 2 2 3 3
1 2 2 4 4 3
1 5 5 4 6 3
5 5 7 4 6 6
8 7 7 7 9 6
8 8 8 9 9 9

样例 1 解释

数据组 3 的合法输出之一:

数据规模与约定

本题采用捆绑测试。

  • Subtask 1(20 pts):k=1k=1
  • Subtask 2(30 pts):n=1n=1
  • Subtask 3(50 pts):没有特殊限制。

对于 100%100\% 的数据,1n,m,k,T,nm1061\le n,m,k,T,\sum nm\le10^{6}