给定一个点双连通的[^1]平面图[^3][^5] $G$。在该图中，至多两个面^7被奇数条边围成。我们还给出了图 $G$ 在平面上的一个平面嵌入。你的任务是判断是否可以将图 $G$ 的边划分为若干个偶数长度的简单环[^8]。

[^1]: 点双连通图是指，对于每一个 $v$ ∈ $V$，图 $(V \setminus {v}, E)$ 是连通的[^2]。

[^2]: 连通图是指，对于任意非空子集划分 $V_1, V_2 \subseteq V$，满足 $V_1 \cap V_2 = \emptyset$ 且 $V_1 \cup V_2 = V$，总存在一条边 $uv \in E$，其中 $u \in V_1$ 且 $v \in V_2$。

[^3]: 图是一个二元组 $(V, E)$，其中 $E$ 是由 $V$ 的二元子集组成的多重集合^4。

[^5]: 如果一个图 $G = (V, E)$ 存在一个嵌入平面的平面嵌入^6，则称其为平面图。

[^8]: 如果边集 $C \subseteq E$ 构成一个连通图，且每个顶点正好连接两条边，则称其为简单环。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 1,000,000$，$1 \le m \le 5,000,000$）。其中 $n$ 表示图 $G$ 中的顶点数，$m$ 表示边数。顶点编号为 1 到 $n$，边编号为 1 到 $m$。每条边连接两个不同的顶点。两顶点之间可以有多条边。

接下来 $n$ 行描述图的边信息。第 $i$ 行描述与顶点 $i$ 相邻的边。该行以一个整数 $s_i$ 开头（$1 \le s_i \le m$），随后是 $s_i$ 个整数，范围从 1 到 $m$，表示与顶点 $i$ 相邻的边的编号。列表中边的顺序是沿顺时针方向排列的。

输出格式

如果无法进行所要求的边划分，输出一行 NIE。

否则，第一行输出 TAK。接下来的每一行描述一个简单环。每行以一个整数 $j$ 开头（$2 \le j \le n$），表示该环的长度，随后是该环所包含的 $j$ 条边的编号。每对相邻边应共享一个顶点。每条边应且只应在输出中出现一次。

示例

输入

10 16
2 1 8
2 8 7
4 1 9 2 14
4 6 13 7 14
4 16 10 9 15
4 16 15 13 12
4 2 10 3 11
4 5 12 6 11
2 3 4
2 4 5

输出

TAK
6 16 10 3 4 5 12
4 6 11 2 14
6 8 1 9 15 13 7