[AdditionalFile5587.zip](file://AdditionalFile5587.zip?type=additional_file)

#5587. 「PA 2017 Final」Galeria handlowa

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

题目译自 PA 2017 Final Galeria handlowa

Bitocy 被父母派到附近的购物中心去购买 $m$ 件商品。因为他喜欢逛商店，所以他计划光顾所有的销售点。他打算每家商店都只进去一次。Bitocy 将按照自己选择的顺序进入这些商店，并在其中一些商店购买清单上尚未购买的某些商品。

众所周知，有些商品可能会在多家商店出售。不幸的是，Bitocy 是个很特别的人，他非常害怕被保安检查。因此，他希望避免这样一种情况：带着一件已经买好的商品，进入一家同样出售该商品的商店。

是否存在一种逛商店和购物的策略，既能让 Bitocy 买齐所有 $m$ 件商品，又能避免与保安发生不愉快的冲突？请帮助他！

输入格式

输入的第一行包含两个整数 $n, m$ $(1 \le n, m \le 1000)$，分别表示购物中心的商店数量和 Bitocy 必须购买的商品数量。

接下来的 $n$ 行描述了购物中心里的商店；其中的第 $i$ 行描述了第 $i$ 家商店。该行首先包含一个整数 $k_i$ $(1 \le k_i \le m)$，表示第 $i$ 家商店的商品种类中，包含在 Bitocy 购物清单上的商品数量。紧随其后的是这些商品的编号，按升序给出。商品用从 $1$ 到 $m$ 的整数进行编号。

输出格式

如果不存在可行的购物策略，则在输出一行 NIE。

否则，输出的第一行应包含 TAK。第二行应包含 $n$ 个从 $1$ 到 $n$ 的不同整数，即依次访问的商店的编号。第三行也是最后一行，应包含 $m$ 个从 $1$ 到 $n$ 的整数；其中第 $i$ 个数字指明了 Bitocy 应该购买第 $i$ 件商品的商店编号。如果存在多个正确答案，你可以输出其中任意一个。

样例

输入

4 4
1 2
2 2 4
2 1 3
1 1

输出

TAK
4 2 1 3
3 1 3 2

首先，Bitocy 应该去 $4$ 号商店，但什么也不买。然后，他去 $2$ 号商店购买第 $4$ 件商品。接下来，在 $1$ 号商店购买第 $2$ 件商品。剩下的商品他将在 $3$ 号商店购买。