You are given a biconnected$^{1}$ planar$^{5}$ graph $G$. In this graph, at most two faces$^{7}$ are bounded by an odd number of edges. You are also given a planar embedding of the graph $G$ in the plane. Determine whether there exists a partition of the edges of $G$ into a number of simple cycles$^{8}$ of even length.

$^{1}$A biconnected graph is a graph $G = (V, E)$ such that for every $v \in V$, the graph $(V \setminus \{v\}, E)$ is connected$^{2}$.

$^{2}$A connected graph is a graph $G = (V, E)$ such that for every partition into non-empty subsets $V_1, V_2 \subseteq V$, $V_1 \cap V_2 = \emptyset$, $V_1 \cup V_2 = V$, there exists an edge $uv \in E$ such that $u \in V_1$ and $v \in V_2$.

$^{3}$A graph is a pair $(V, E)$, where $E$ is a multiset$^{4}$ of two-element subsets of $V$.

$^{4}$A multiset is a set in which elements can repeat; formally, it is a function from an arbitrary set to the set of natural numbers.

$^{5}$A graph $G = (V, E)$ is called planar if there exists a planar embedding$^{6}$ of this graph in the plane.

$^{6}$A planar embedding of a planar graph in the plane is a drawing of the graph in which each vertex is assigned a distinct point in the plane, and each edge is assigned a curve connecting the points assigned to the vertices connected by that edge. Each curve may intersect another vertex or curve only at its endpoints.

$^{7}$Consider a planar embedding of a planar graph in the plane. A face of the graph is any region of the plane bounded by the curves corresponding to the edges. Note that in every graph, there is also an infinite face "surrounding" the graph.

$^{8}$A set of edges $C \subseteq E$ is called a simple cycle if these edges form a connected graph in which every vertex is incident to exactly two edges.

Input

The first line of the input contains two integers $n$ and $m$ ($2 \le n \le 1\,000\,000$, $1 \le m \le 5\,000\,000$). The number $n$ denotes the number of vertices, and $m$ denotes the number of edges in the graph $G$. The vertices are numbered from 1 to $n$, and the edges are numbered from 1 to $m$. Each edge connects two distinct vertices. There may be multiple edges between a given pair of vertices.

This is followed by $n$ lines describing the edges of the graph; the $i$-th of these lines contains a description of the edges incident to vertex $i$. This description begins with an integer $s_i$ ($1 \le s_i \le m$), followed by a list of $s_i$ integers in the range from 1 to $m$. Each of these numbers denotes the index of one edge incident to vertex $i$. The list contains the edges ordered sequentially around vertex $i$, in clockwise order.

Output

If such a partition of edges does not exist, print the word NIE in the only line of the output.

Otherwise, print the word TAK in the first line of the output. In the following lines, print a valid partition of the edges of $G$ into simple cycles. Each of these lines should start with an integer $j$ ($2 \le j \le n$). After it, print $j$ edge indices forming the described simple cycle. Every two consecutive edges should share a common vertex. Each edge should be printed in the output exactly once.

Examples

Input 1

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

Output 1

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