Matches

On a Saturday morning, $n$ boys gather on the field of the "Bajtusie" sports club. The number of boys is always even, so all of them can split into two teams and enjoy a game of football.

Bajtazar, the club's coach, is in charge of the lineup for each match. The boys love to compete, so he wants to arrange the teams so that every two boys get to face each other on opposing teams in at least one match.

Bajtazar has already fixed the lineups for the upcoming $m$ matches. In every match all boys play, split into two teams of $n/2$ players each. Determine whether, across the planned matches, every pair of boys ends up on opposing teams at least once.

The first line contains two integers $n$ and $m$ ($4 \le n \le 40000$, $1 \le m \le 50$): the number of boys and the number of planned matches. Each boy wears a distinct shirt number, an integer from $1$ to $n$.

Each of the next $m$ lines describes the lineup of one match and contains $n$ pairwise distinct integers from $1$ to $n$. The first $n/2$ numbers are the players of the first team, and the remaining $n/2$ numbers are the players of the second team.

Print a single word: TAK if every pair of boys faces each other on opposing teams in at least one match, or NIE otherwise.