Planar Graph

Memory limit: 512 MB

You are given a two-vertex-connected\footnote{A graph is two-vertex-connected if for any , the graph is connected\footnotemark{}.}\footnotetext{A graph is connected, if for each partition into non-empty subsets there exists an edge , such that and .} planar\footnote{A graph is planar, if there exists a planar embedding\footnotemark{} of into the plane.} \footnotetext{A planar embedding of a planar graph into the plane is such its drawing, where each vertex is assigned a point, whereas each edge is assigned a curve connecting the points assigned to the endpoints of the edge. Two curves corresponding to edges may intersect only in their endpoints.} graph\footnote{A graph is a pair , where is a multiset\footnotemark{} of two-element subsets of .}\footnotetext{A multiset is a set in which an element may appear several times; formally, a multiset is a function from any set into the set of natural numbers N.} . In this graph at most two faces\footnote{Consider a planar embedding of a planar graph into the plane. Each of the regions bounded by the curves corresponding to edges is called a face. Note that in each planar graph there exists an infinite face "surrounding" the graph.} are surrounded by an odd number of edges. You are also given a planar embedding of the graph . You should verify whether there exists a partition of the edges of into a number of simple cycles\footnote{A set of edges is a simple cycle, if the edges of form a connected graph in which each vertex is adjacent to exactly two edges.} of even length.

Input

The first line of input contains two integers and (, ), denoting the number of vertices and edges of the graph . Vertices are numbered to , whereas edges are numbered to . Each edge connects two different vertices. A pair of vertices may be connected by several edges.

The following lines describe the edges of the graph. The -th of those lines contains a description of edges incident to the vertex ; the description starts with an integer (), followed by a list of integers between and . Each of those numbers represents an edge adjacent to the vertex . Moreover the list of edges is sorted clockwise with respect to the vertex .

Output

If a desired partition of the edges does not exist, then your program should output NIE (Polish for no).

Otherwise the first line of output should contain TAK (Polish for yes). The following lines should contain a valid partition of the edges of into simple cycles. Each of those lines should start with an even integer (), followed by indices of edges belonging to the described simple cycle. Every two consecutive edges should have a common endpoint. Each edge of should appear in the output exactly once.

Example

For the input data:

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

the correct result is:

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