P6663 [POI 2019/2020 R1] Układ scalony / 集成电路

Bajtel 公司专门生产集成电路板。 --- 因为数据较多，所以 Subtask 1 的另一部分挪到了 [这里](https://www.luogu.com.cn/problem/U122678)。

Bajtel 公司生产的集合电路板的大小为 $n \times m$，现在通电的格子为 $(1,1)$。 我们可以在两个相邻的格子连上电路让一个格子的电通向另一个格子，若干个电路组成集合电路。 现在我们要连 $n \times m-1$ 条电路，并且要求最长的集合电路 **恰好** 长度为 $k$，并且要求 **让所有格子通电**。 求一种连接电路的方式。

一行三个整数 $n,m,k$ 代表电路板的大小和最长的集合电路必须满足的长度。

如果没有满足题意的连接方式，输出一个字符串 `NIE` 并结束程序。 如果有满足题意的连接方式： 第一行一个字符串 `TAK`。 接下来 $n \times m-1$ 行每行四个整数 $u_1,v_1,u_2,v_2$ 代表一个电路连接 $(u_1,v_1)$，$(u_2,v_2)$。 如果有多组满足题意的解，输出一组即可。

#### 样例说明 对于样例 $1$，如下图  另一组附加样例请见附加文件中的 sample.zip。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（20 pts）：$n,m \le 6$。 - Subtask 2（20 pts）：$n \le 3$。 - Subtask 3（30 pts）：$n \times m$ 为奇数。 - Subtask 4（30 pts）：$n \times m$ 为偶数。 对于 $100\%$ 的数据，$1 \le n,m \le 1000$，$0 \le k \le 10^6$。 如果您输出了 `TAK`（并且这个数据点的确有解），但是您在后面电路连接的描述中出错，您可以获得 $20\%$ 的分数。 #### 说明 翻译自 [POI 2019](https://sio2.mimuw.edu.pl/c/oi27-1/dashboard/) E [Układ scalony](https://sio2.mimuw.edu.pl/c/oi27-1/p/ukl/)。